International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

09:17 [Pub][ePrint] Time-release Protocol from Bitcoin and Witness Encryption for SAT, by Jia Liu and Flavio Garcia and Mark Ryan

  We propose a new time-release protocol based on the bitcoin protocol and witness encryption. We derive a ``public key\'\' from the bitcoin block chain for encryption. The decryption key are the unpredictable information in the future blocks (e.g., transactions, nonces)

that will be computed by the bitcoin network. We build this protocol by witness encryption and encrypt with the bitcoin proof-of-work constraints. The novelty of our protocol is that the decryption key will be automatically and publicly available in the bitcoin block chain when the time is due.

Witness encryption was originally proposed by Garg, Gentry, Sahai and Waters. It provides a means to encrypt to an instance, $x$, of an NP language and to decrypt by a witness $w$ that $x$ is in the language.

Encoding CNF-SAT in the existing witness encryption schemes generate poly(n*k) group elements in the ciphertext where n is the number of variables and k is the number of clauses of the CNF formula.

We design a new witness encryption for CNF-SAT which achieves ciphertext size of 2n+2k group elements. Our witness encryption is based on an intuitive reduction from SAT to Subset-Sum problem. Our scheme uses the framework of multilinear maps, but it is independent of the implementation details of multilinear maps.

21:17 [Pub][ePrint] A Provably Secure Group Signature Scheme from Code-Based Assumptions, by Martianus Frederic Ezerman and Hyung Tae Lee and San Ling and Khoa Nguyen and Huaxiong Wang

  We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than all of the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ($\\approx 2^{24}$ users).

The feasibility of the scheme is supported by implementation results.

Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

21:17 [Pub][ePrint] Trinocchio: Privacy-Friendly Outsourcing by Distributed Verifiable Computation, by Berry Schoenmakers, Meilof Veeningen, and Niels de Vreede

  Verifiable computation allows a client to outsource computations to a worker with a cryptographic proof of correctness of the result that can be verified faster than performing the computation. Recently, the Pinocchio system achieved faster verification than computation in practice for the first time. Unfortunately, Pinocchio and other efficient verifiable computation systems require the client to disclose the inputs to the worker, which is undesirable for sensitive inputs. To solve this problem, we propose Trinocchio: a system that distributes Pinocchio to three (or more) workers, that each individually do not learn which inputs they are computing on. Each worker essentially performs the work for a single Pinocchio proof; verification by the client remains the same. Moreover, we extend Trinocchio to enable joint computation with multiple mutually distrusting inputters and outputters and still very fast verification. We show the feasibility of our approach by analysing the performance of an implementation in two case studies.

21:17 [Pub][ePrint] Advanced Differential Cryptanalysis of Reduced-Round SIMON64/128 Using Large-Round Statistical Distinguishers, by Theodosis Mourouzis and Guangyan Song and Nicolas Courtois and Michalis Christofii

  Lightweight cryptography is a rapidly evolving area of research and it has great impact especially on the new computing environment called the Internet of Things (IoT) or the Smart Object networks (Holler et al., 2014), where lots of constrained devices are connected on the Internet and exchange information on a daily basis. Every year there are many new submissions of cryptographic primitives which are optimized towards both software and hardware implementation so that they can operate in devices which have limited resources of hardware and are subject to both power and energy consumption constraints. In 2013, two families of ultra-lightweight block ciphers were proposed, SIMON and SPECK, which come in a variety of block and key sizes and were designed to be optimized in hardware and software implementation respectively (Beaulieu et al., 2013). In this paper, we study the security of the 64-bit SIMON with 128-bit key against advanced forms of differential cryptanalysis using truncated differentials (Knudsen, 1995; Courtois et al., 2014a). We follow similar method as the one proposed in SECRYPT 2013 (Courtois and Mourouzis, 2013) in order to heuristically discover sets of differences that propagate with sufficiently good probability and allow us to combine them efficiently in order to construct large-round statistical distinguishers. We present a 22-round distinguisher which we use it in a depth-first key search approach to develop an attack against 24 and 26 rounds with complexity 2^{124.5} and 2^{126} SIMON encryptions respectively. Our methodology provides a framework for extending distinguishers to attacks to a larger number of rounds assuming truncated differential properties of relatively high probability were discovered.

21:17 [Pub][ePrint] VARIANTS OF DIFFERENTIAL AND LINEAR CRYPTANALYSIS, by Mehak Khurana and Meena Kumari

  Block cipher is in vogue due to its requirement for integrity, confidentiality and authentication. Differential and Linear cryptanalysis are the basic techniques on block cipher and till today many cryptanalytic attacks are developed based on these. Each variant of these have different methods to find distinguisher and based on the distinguisher, the method to recover key. This paper illustrates the steps to find distinguisher and steps to recover key of all variants of differential and linear attacks developed till today. This is advantageous to cryptanalyst and cryptographer to apply various attacks simultaneously on any crypto algorithm.

21:17 [Pub][ePrint] Fully Homomorphic Encryption without bootstrapping, by Masahiro Yagisawa

  Gentry\'s bootstrapping technique is the most famous method of obtaining fully homomorphic encryption. In this paper I propose a new fully homomorphic encryption scheme on non-associative octonion ring over finite field without bootstrapping technique. The security of the proposed fully homomorphic encryption scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. Because proposed fully homomorphic encryption scheme is based on multivariate algebraic equations with high degree or too many variables, it is against the Gröbner basis attack, the differential attack, rank attack and so on.

The key size of this system and complexity for enciphering/deciphering become to be small enough to handle.

21:17 [Pub][ePrint] Randomizing Scalar Multiplication Using Exact Covering Systems of Congruences, by Eleonora Guerrini and Laurent Imbert and Théo Winterhalter

  In this paper we present a generic, uniformly randomized scalar multiplication algorithm based on covering systems of congruences, with built-in protections against various side-channel attacks. It has been tailored to resist a recent class of attacks called horizontal attacks. These very powerful attacks exploit some unsuspected weaknesses hidden in most, if not all, highly regular and constant time algorithms.

We provide a thorough complexity analysis, several arguments to support its robustness and some encouraging numerical experiments.

21:17 [Pub][ePrint] XPX: Generalized Tweakable Even-Mansour with Improved Security Guarantees, by Bart Mennink

  We present XPX, a tweakable blockcipher based on a single permutation P. On input of a tweak (t_{11},t_{12},t_{21},t_{22}) in mathcal{T} and a message m, it outputs ciphertext c=P(m xor Delta_1) xor Delta_2, where Delta_1=t_{11}k xor t_{12}P(k) and Delta_2=t_{21}k xor t_{22}P(k). Here, the tweak space mathcal{T} is required to satisfy a certain set of trivial conditions (such as (0,0,0,0) not in mathcal{T}). We prove that XPX with any such tweak space is a strong tweakable pseudorandom permutation. Next, we consider the security of XPX under related-key attacks, where the adversary can freely select a key-deriving function upon every evaluation. We prove that XPX achieves various levels of related-key security, depending on the set of key-deriving functions and the properties of mathcal{T}. For instance, if t_{12},t_{22} neq 0 and (t_{21},t_{22}) neq (0,1) for all tweaks, XPX is XOR-related-key secure.

XPX generalizes Even-Mansour (EM), but also Rogaway\'s XEX based on EM, and tweakable EM used in Minalpher. As such, XPX finds a wide range of applications. We show how our results on XPX directly imply related-key security of the authenticated encryption schemes Pr{\\o}st-COPA and Minalpher, and how a straightforward adjustment to the MAC function Chaskey and to keyed Sponges makes them provably related-key secure.

21:17 [Pub][ePrint] Authentication Key Recovery in Galois/Counter Mode (GCM), by John Mattsson

  GCM is used in a vast amount of security protocols and is quickly becoming the de facto mode of operation for block ciphers. In this paper we suggest several novel improvements to Fergusons\'s authentication key recovery method and show that for many truncated tag sizes, the security levels are far below, not only the current NIST requirement of 112-bit security, but also the old NIST requirement of 80-bit security. We therefore strongly recommend NIST to make a revision of SP 800-38D.

21:17 [Pub][ePrint] How to Build Time-Lock Encryption, by Tibor Jager

  Time-lock encryption is a method to encrypt a message such that it can only be decrypted after a certain deadline has passed. A computationally powerful adversary should not be able to learn the message before the deadline. However, even receivers with relatively weak computational resources should immediately be able to decrypt after the deadline, without any interaction with the sender, other receivers, or a trusted third party.

We show how to realize this strong notion of secure encryption by making the additional, very realistic assumption that intermediate results of an iterative, public, large-scale computation --- like the computations performed by users of the popular cryptocurrency Bitcoin --- are publicly available. We use these computations as a \"computational reference clock\", which mimics a physical clock in a computational setting, and show how the computations performed by the reference clock can be \"reused\" to build secure time-lock encryption. A nice feature of this approach is that it can be based on a public computation which is performed \"anyway\" and independent of the time-lock encryption scheme.

We provide the first formal definitions of computational reference clocks and time-lock encryption, and give a proof-of-concept construction which combines a computational reference clock with witness encryption (Garg et al., STOC 2013). We also explain how to construct a computational reference clock based on Bitcoins.

09:17 [Pub][ePrint] Shadow-Bitcoin: Scalable Simulation via Direct Execution of Multi-threaded Applications, by Andrew Miller and Rob Jansen

  We describe a new methodology that enables the di-

rect execution of multi-threaded applications inside of

Shadow, an existing parallel discrete-event network sim-

ulation framework. Our methodology utilizes function

interposition and an application-layer thread library to

emulate the ordinary thread interface to the application.

Using this methodology, we implement a new Shadow

plug-in that directly executes the Bitcoin reference client

software. We describe optimizations that enable scalable

execution of thousands of Bitcoin nodes on a single ma-

chine, and discuss how to model the Bitcoin network for

experimental purposes. Finally, we present novel denial-

of-service attacks against the Bitcoin software, which

exploit low-level implementation artifacts in the Bitcoin

reference client. We demonstrate these attacks using our

methodology, tools, and models.