International Association for Cryptologic Research

# IACR News Central

Here you can see all recent updates to the IACR webpage. These updates are also available:

Now viewing news items related to:

29 April 2017
Event date: 29 November to 2 December 2017
28 April 2017
We consider the problem of solving multivariate systems of Boolean polynomial equations: starting from a system of $m$ polynomials of degree at most $d$ in $n$ variables, we want to find its solutions over $\F_2$. Except for $d=1$, the problem is known to be NP-hard, and its hardness has been used to create public cryptosystems; this motivates the search for faster algorithms to solve this problem. After reviewing the state of the art, we describe a new algorithm and show that it outperforms previously known methods in a wide range of relevant parameters. In particular, the first named author has been able to solve all the Fukuoka Type~I MQ challenges, culminating with the resolution of a system of 148 quadratic equations in 74 variables in less than a day (and with a lot of luck).
In present paper, we mainly investigate the problem of efficiently constructing lightweight orthogonal MDS matrices over the matrix polynomial residue ring. Surprisingly, this problem did not receive much attention previously. We propose a necessary-and-sufficient condition, which is more efficient than the traditional method, about judging whether an orthogonal matrix is MDS. Although it has been proved that the circulant orthogonal MDS matrix does not exist over the finite field, we discuss anew this problem and get a new method to judge which polynomial residue ring can be used to construct the circulant orthogonal MDS matrix. According to this method, the minimum polynomials of non-singular matrices over $\FF$ are factorized. With these results of factorizations, finally, we propose an extremely efficient algorithm for constructing lightweight circulant orthogonal MDS matrices. By using this algorithm, a lot of new lightweight circulant orthogonal MDS matrices are constructed for the first time.
In 2015, Chou and Orlandi presented an oblivious transfer protocol that already drew a lot of attention both from theorists and practitioners due to its extreme simplicity and high efficiency. Chou and Orlandi claimed that their protocol is UC-secure under dynamic corruptions, which is a very strong security guarantee. Unfortunately, in this work we point out a serious flaw in their security proof. Moreover, we show that their protocol cannot be proven UC-secure even under static corruptions unless some computational assumption, which we conjecture to hold, is false.
Secure multi-party computation allows a number of participants to securely evaluate a function on their private inputs and has a growing number of applications. Two standard adversarial models that treat the participants as semi-honest or malicious, respectively, are normally considered for showing security of constructions in this framework. In this work, we go beyond the standard security model in the presence of malicious participants and treat the problem of enforcing correct inputs to be entered into the computation. We achieve this by having a certification authority certify user's information, which is consequently used in secure two-party computation based on garbled circuit evaluation. The focus of this work on enforcing correctness of garbler's inputs via certification, as prior work already allows one to achieve this goal for circuit evaluator's input. Thus, in this work, we put forward a novel approach for certifying user's input and tying certification to garbler's input used during secure function evaluation based on garbled circuits. Our construction achieves notable performance of adding only one (standard) signature verification and $O(n\rho)$ symmetric key/hash operations to the cost of garbled circuit evaluation in the malicious model via cut-and-choose, in which $\rho$ circuits are garbled and $n$ is the length of the garbler's input in bits. Security of our construction is rigorously proved in the standard model.
ePrint Report Analysis of Toeplitz MDS Matrices Sumanta Sarkar, Habeeb Syed
This work considers the problem of constructing efficient MDS matrices over the field $\F_{2^m}$. Efficiency is measured by the metric XOR count which was introduced by Khoo et al. in CHES 2014. Recently Sarkar and Syed (ToSC Vol. 1, 2016) have shown the existence of $4\times 4$ Toeplitz MDS matrices with optimal XOR counts. In this paper, we present some characterizations of Toeplitz matrices in light of MDS property. Our study leads to improving the known bounds of XOR counts of $8\times 8$ MDS matrices by obtaining Toeplitz MDS matrices with lower XOR counts over $\F_{2^4}$ and $\F_{2^8}$.
ePrint Report Forking-Free Hybrid Consensus with Generalized Proof-of-Activity Shuyang Tang, Zhiqiang Liu, Sherman S. M. Chow, Zhen Liu, Yu Long, Shengli Liu
Bitcoin and its underlying blockchain mechanism have been attracting much attention. One of their core innovations, Proof-of-Work (PoW), is notoriously inefficient and potentially motivates a centralization of computing power, which defeats the original aim of decentralization. Proof-of-Stake (PoS) is later proposed to replace PoW. However, both PoW and PoS have different inherent advantages and disadvantages, so does Proof-of-Activity (PoA) of Bentov et al. (SIGMETRICS 2014) which only offers limited combinations of two mechanisms. On the other hand, the hybrid consensus protocol of Pass and Shi (ePrint 2016/917) aims to improve the efficiency by dynamically maintaining a rotating committee. Yet, there are unsatisfactory issues including selfish mining and fair committee election. In this paper, we firstly devise a generalized variant of PoW. After that, we leverage our newly proposed generalized PoW to construct forking-free hybrid consensus, which addresses issues faced by a regular hybrid consensus mechanism. We further combine our forking-free hybrid consensus mechanism with PoS for a generalization of PoA. Compared with PoA, our generalized PoA improves the efficiency and provides more flexible combinations of PoW and PoS, resulting in a more powerful and applicable consensus scheme.
ePrint Report BitFlip: A Randomness-Rich Cipher Gideon Samid, Serguei Popov
We present a cipher that represents a novel strategy: replacing algorithmic complexity with computational simplicity while generating cryptographic efficacy through large as desired quantities of randomness. The BitFlip cipher allows its user to defend herself with credibly appraised mathematical intractability, well-hinged on solid combinatorics. This is the situation when the amount of randomness is small relative to the accumulated amount of processed plaintext. Deploying more randomness, BitFlip will frustrate its cryptanalyst with terminal equivocation among two or more plausible message candidates. This equivocation defense can be increased by simply increasing the amount of deployed randomness, coming at-will close to Vernam’s perfect secrecy. BitFlip is structured as a super polyalphabetic cipher where a letter comprised of 2n bits is pointed-to by any 2n bits string with a Hamming distance of n from it. When a passed 2n bits string is found to have no n-valued Hamming distance from any letter in the reader’s alphabet, it is regarded as null. This allows for co-encryption of several messages each over its respective alphabet; thereby offering a powerful equivocation defense because the ciphertext does not indicate which alphabet the intended reader is using. BitFlip becomes increasingly timely and practical, exploiting the advent of high quality non-algorithmic randomness, as well as the effect of Moore’s law on the cost of handling large amounts of memory. BitFlip is a natural fit for what fast emerges as the biggest customer of cryptography: the Internet of Things
We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for public-key encryption schemes, and the types of evidence we have for the veracity of these assumptions.

This survey/tutorial was published in the book "Tutorials on the Foundations of Cryptography", dedicated to Oded Goldreich on his 60th birthday.
26 April 2017
CHES 2017 CTF Challenge : The WhibOx Contest
An ECRYPT White-Box Cryptography Competition

Can you obfuscate an AES encryption in practice? Can you break a secretly obfuscated AES program?

Starting from May 15, the EU-sponsored ECRYPT-CSA project is organising an open competition on white-box cryptography.

The competition comes in two flavors for competitors:
• Developers are invited to post challenge programs that are white-box implementations of AES-128 under freely chosen keys. Challenges are expected to resist key extraction against a white-box attacker.
• Attackers are invited to break the submitted challenges i.e. extract their hard-coded encryption key.
Participants may remain _completely anonymous_ or use their real-life identity, as they prefer. Implementers are not expected to explain their designs: they only have to provide a resulting C code. Attackers are not expected to explain their techniques: they only have to recover and provide the embedded key(s).

Important Dates:

May 15, 2017: Competition starting date, submission server opens
Aug 31, 2017: Submission deadline (attacks continue)
Sep 24, 2017: Final deadline (attacks stop)
CHES 2017 rump session: Announcement of winners

More details on: http://whibox.cr.yp.to/
An important benchmark for multi-party computation protocols (MPC) is their round complexity. For several important MPC tasks, (tight) lower bounds on the round complexity are known. However, for some of these tasks, such as broadcast, the lower bounds can be circumvented when the termination round of every party is not a priori known, and simultaneous termination is not guaranteed. Protocols with this property are called \emph{probabilistic-termination (PT)} protocols.

Running PT protocols in parallel affects the round complexity of the resulting protocol in somewhat unexpected ways. For instance, an execution of $m$ protocols with constant expected round complexity might take $O(\log m)$ rounds to complete. In a seminal work, Ben-Or and El-Yaniv (Distributed Computing '03) developed a technique for parallel execution of arbitrarily many broadcast protocols, while preserving expected round complexity. More recently, Cohen et al.(CRYPTO '16) devised a framework for universal composition of PT protocols, and provided the first composable parallel-broadcast protocol with a simulation-based proof. These constructions crucially rely on the fact that broadcast is "privacy free," and do not generalize to arbitrary protocols in a straightforward way. This raises the question of whether it is possible to execute arbitrary PT protocols in parallel, without increasing the round complexity.

In this paper we tackle this question and provide both feasibility and infeasibility results. We construct a round-preserving protocol compiler, secure against a dishonest minority of actively corrupted parties, that compiles arbitrary protocols into a protocol realizing their parallel composition, while having a black-box access to the underlying \emph{protocols}. Furthermore, we prove that the same cannot be achieved, using known techniques, given only black-box access to the \emph{functionalities} realized by the protocols, unless merely security against semi-honest corruptions is required, for which case we provide a protocol.

To prove our results, we utilize the language and results by Cohen et al., which we extend to capture parallel composition and reactive functionalities, and to handle the case of an honest majority.
ePrint Report TOPPSS: Cost-minimal Password-Protected Secret Sharing based on Threshold OPRF Stanislaw Jarecki, Aggelos Kiayias, Hugo Krawczyk, Jiayu Xu
We present TOPPSS, the most efficient Password-Protected Secret Sharing (PPSS) scheme to date. A (t; n)-threshold PPSS, introduced by Bagherzandi et al, allows a user to share a secret among n servers so that the secret can later be reconstructed by the user from any subset of t+1 servers with the sole knowledge of a password. It is guaranteed that any coalition of up to t corrupt servers learns nothing about the secret (or the password). In addition to providing strong protection to secrets stored online, PPSS schemes give rise to efficient Threshold PAKE (T-PAKE) protocols that armor single-server password authentication against the inherent vulnerability to offline dictionary attacks in case of server compromise.

TOPPSS is password-only, i.e. it does not rely on public keys in reconstruction, and enjoys remarkable efficiency: A single communication round, a single exponentiation per server and just two exponentiations per client regardless of the number of servers. TOPPSS satis es threshold security under the (Gap) One-More Diffie-Hellman (OMDH) assumption in the random-oracle model as in several prior efficient realizations of PPSS/TPAKE. Moreover, we show that TOPPSS realizes the Universally Composable PPSS notion of Jarecki et al under a generalization of OMDH, the Threshold One-More Diffie-Hellman (T-OMDH) assumption. We show that the T-OMDH and OMDH assumptions are both hard in the generic group model.

The key technical tool we introduce is a universally composable Threshold Oblivious PRF which is of independent interest and applicability.
Since its introduction the UC framework by Canetti has received a lot of attention. A contributing factor to its popularity is that it allows to capture a large number of common cryptographic primitives using ideal functionalities and thus can be used to give modular proofs for many cryptographic protocols. However, an important member of the cryptographic family has not yet been captured by an ideal functionality, namely the zero-knowledge proof of membership. We give the first formulation of a UC zero-knowledge proof of membership and show that it is closely related to the notions of straight-line zero-knowledge and simulation soundness.
We show that indistinguishability obfuscation (IO) for all circuits can be constructed solely from secret-key functional encryption (SKFE). In the construction, SKFE need to be able to issue a-priori unbounded number of functional keys, that is, collusion-resistant.

Our strategy is to replace public-key functional encryption (PKFE) in the construction of IO proposed by Bitansky and Vaikuntanathan (FOCS 2015) with puncturable SKFE. Bitansky and Vaikuntanathan introduced the notion of puncturable SKFE and observed that the strategy works. However, it has not been clear whether we can construct puncturable SKFE without assuming PKFE. In particular, it has not been known whether puncturable SKFE is constructed from ordinary SKFE.

In this work, we show that a relaxed variant of puncturable SKFE can be constructed from collusion-resistant SKFE. Moreover, we show that the relaxed variant of puncturable SKFE is also sufficient for constructing IO.
Three-party Password Authenticated Key Exchange (3PAKE) protocol is an important cryptographic primitive, where clients can establish a session key using easy-to-remember passwords. A number of 3PAKE protocols based on traditional mathematical problems have been presented in the literature, but these protocols are not able to resist attacks using quantum computers. In this paper, we construct the first 3PAKE protocol from lattices. Lattice-based cryptography is a promising post-quantum cryptography approach. We then prove its security in the random oracle model, and implement the proposed protocol using LatticeCrypto. The implementation results shows our protocol is very efficient in practice.
ePrint Report New Protocols for Conditional Disclosure of Secrets (and More) Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee
We present new protocols for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$, we present two protocols that achieve $o(N^{1/2})$ communication: the first achieves $O(N^{1/3})$ communication and the second achieves sub-polynomial $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$ communication.

- As a corollary, we obtain improved share complexity for forbidden graph access structures. Namely, for every graph on $N$ vertices, there is a secret-sharing scheme for $N$ parties in which each pair of parties can reconstruct the secret if and only if the corresponding vertices in $G$ are connected, and where each party gets a share of size $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$.

Prior to this work, the best protocols for both primitives required communication complexity $\tilde{O}(N^{1/2})$. Indeed, this is essentially the best that all prior techniques could hope to achieve as they were limited to so-called linear reconstruction''. This is the first work to break this $O(N^{1/2})$ linear reconstruction'' barrier in settings related to secret sharing. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval.

We further extend our results to the setting of private simultaneous messages (PSM), and provide applications such as an improved attribute-based encryption (ABE) for quadratic polynomials.
ePrint Report Almost Optimal Oblivious Transfer from QA-NIZK Olivier Blazy, Céline Chevalier, Paul Germouty
We show how to build a UC-Secure Oblivious Transfer in the presence of Adaptive Corruptions from Quasi-Adaptive Non-Interactive Zero-Knowledge proofs. Our result is based on the work of Jutla and Roy at Asiacrypt 2015, where the authors proposed a constant-size very efficient PAKE scheme. As a stepping stone, we first show how a two-flow PAKE scheme can be generically transformed in an optimized way, in order to achieve an efficient three-flow Oblivious-Transfer scheme. We then compare our generic transformations to existing OT constructions and see that we manage to gain at least a factor 2 to the best known constructions. To the best of our knowledge, our scheme is the first UC-secure Oblivious Transfer with a constant size flow from the receiver, and nearly optimal size for the server.
We present an information-theoretically secure continuously non-malleable code in the constant split-state model, where there is a self-destruct mechanism which ensures that the adversary loses access to tampering after the first failed decoding.

Prior to our result only codes with computational security were known for this model, and it has been an open problem to construct such a code with information theoretic security.

As a conceptual contribution we also introduce the notion of a one-way non-malleable code, which is the main new ingredient in our construction. In this notion, the tampering adversary's goal is to recover the encoded message rather than to distinguish the encodings of two messages.

Our technical contributions are two-fold. \begin{itemize} \item

We show how to construct a full fledged continuously non-malleable code from a one-way continuously non-malleable code while only increasing the number of states by a constant factor.

\item

We construct a one-way continuously non-malleable code in the constant split state model with information theoretic security.

\end{itemize}
ePrint Report XOR of PRPs in a Quantum World Bart Mennink, Alan Szepieniec
In the classical world, the XOR of pseudorandom permutations $E_{k_1}\xor\cdots\xor E_{k_r}$ for $r\geq2$ is a well-established way to design a pseudorandom function with optimal'' security: security up to approximately $\min\{|K|,|X|\}$ queries, where $K$ and $X$ are the key and state space of the block cipher $E$. We investigate security of this construction against adversaries who have access to quantum computers.

We first present a key recovery attack in $|K|^{r/(r+1)}$ complexity. The attack relies on a clever application of a claw-finding algorithm and testifies of a significant gap with the classical setting where $2$ pseudorandom permutations already yield optimal security.

Next, we perform a quantum security analysis of the construction, and prove that it achieves security up to $\min\{|K|^{1/2}/r,|X|\}$ queries. The analysis relies on a generic characterization of classical and quantum distinguishers and a universal transformation of classical security proofs to the quantum setting that is of general interest.
ePrint Report White-Box Cryptography: Don't Forget About Grey Box Attacks Joppe W. Bos, Charles Hubain, Wil Michiels, Cristofaro Mune, Eloi Sanfelix Gonzalez, Philippe Teuwen
Despite the fact that all current scientific white-box approaches of standardized cryptographic primitives have been publicly broken, these attacks require knowledge of the internal data representation used by the implementation. In practice, the level of implementation knowledge required is only attainable through significant reverse engineering efforts.

In this paper we describe new approaches to assess the security of white-box implementations which require neither knowledge about the look-up tables used nor expensive reverse engineering effort. We introduce the differential computation analysis (DCA) attack which is the software counterpart of the differential power analysis attack as applied by the cryptographic hardware community. Similarly, the differential fault analysis (DFA) attack is the software counterpart of fault-injection attacks on cryptographic hardware.

For DCA, we developed plugins to widely available dynamic binary instrumentation (DBI) frameworks to produce software execution traces which contain information about the memory addresses being accessed. For the DFA attack, we developed modified emulators and plugins for DBI frameworks that allow injecting faults at selected moments within the execution of the encryption or decryption process as well as a framework to automate static fault injection.

To illustrate the effectiveness, we show how DCA and DFA can extract the secret key from numerous publicly available non-commercial white-box implementations of standardized cryptographic algorithms. These approaches allow one to extract the secret key material from white-box implementations significantly faster and without specific knowledge of the white-box design in an automated or semi-automated manner.
ePrint Report Tightly Secure Ring-LWE Based Key Encapsulation with Short Ciphertexts Martin R. Albrecht, Emmanuela Orsini, Kenneth G. Paterson, Guy Peer, Nigel P. Smart
We provide a tight security proof for an IND-CCA Ring-LWE based Key Encapsulation Mechanism that is derived from a generic construction of Dent (IMA Cryptography and Coding, 2003). Such a tight reduction is not known for the generic construction. The resulting scheme has shorter ciphertexts than can be achieved with other generic constructions of Dent or by using the well-known Fujisaki-Okamoto constructions (PKC 1999, Crypto 1999). Our tight security proof is obtained by reducing to the security of the underlying Ring-LWE problem, avoiding an intermediate reduction to a CPA-secure encryption scheme. The proof technique maybe of interest for other schemes based on LWE and Ring-LWE.
Lattice-based group signature is an active research topic in recent years. Since the pioneering work by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010), eight other schemes have been proposed, providing various improvements in terms of security, efficiency and functionality. However, most of the existing constructions work only in the static setting where the group population is fixed at the setup phase. The only two exceptions are the schemes by Langlois et al. (PKC 2014) that handles user revocations (but new users cannot join), and by Libert et al. (Asiacrypt 2016) which addresses the orthogonal problem of dynamic user enrollments (but users cannot be revoked).

In this work, we provide the first lattice-based group signature that offers full dynamicity (i.e., users have the flexibility in joining and leaving the group), and thus, resolve a prominent open problem posed by previous works. Moreover, we achieve this non-trivial feat in a relatively simple manner. Starting with Libert et al.'s fully static construction (Eurocrypt 2016) - which is arguably the most efficient lattice-based group signature to date, we introduce simple-but-insightful tweaks that allow to upgrade it directly into the fully dynamic setting. More startlingly, our scheme even produces slightly shorter signatures than the former. The scheme satisfies the strong security requirements of Bootle et al.'s model (ACNS 2016), under the Short Integer Solution (SIS) and the Learning With Errors (LWE) assumptions.
ePrint Report A low-resource quantum factoring algorithm Daniel J. Bernstein, Jean-François Biasse, Michele Mosca
In this paper, we present a factoring algorithm that, assuming standard heuristics, uses just $(\log N)^{2/3+o(1)}$ qubits to factor an integer $N$ in time $L^{q+o(1)}$ where $L = \exp((\log N)^{1/3}(\log\log N)^{2/3})$ and $q=\sqrt[3]{8/3}\approx 1.387$. For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is $L^{p+o(1)}$ where $p>1.9$. The new time complexity is asymptotically worse than Shor's algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner.
ePrint Report Post-quantum RSA Daniel J. Bernstein, Nadia Heninger, Paul Lou, Luke Valenta
This paper proposes RSA parameters for which (1) key generation, encryption, decryption, signing, and verification are feasible on today's computers while (2) all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor's algorithm and much faster than pre-quantum factorization algorithms. Initial pqRSA implementation results are provided.
ePrint Report The Montgomery ladder on binary elliptic curves Thomaz Oliveira, Julio López, Francisco Rodr&#305;&#769;guez-Henr&#305;&#769;quez
In this survey paper we present a careful analysis of the Montgomery ladder procedure applied to the computation of the constant-time point multiplication operation on elliptic curves defined over binary extension fields. We give a general view of the main improvements and formula derivations that several researchers have contributed across the years, since the publication of Peter Lawrence Montgomery seminal work in 1987. We also report a fast software implementation of the Montgomery ladder applied on a Galbraith-Lin-Scott (GLS) binary elliptic curve that offers a security level close to 128 bits. Using our software we can execute the ephemeral Diffie-Hellman protocol in just 95,702 clock cycles when implemented on an Intel Skylake machine running at 4 GHz.
Quantum computing poses challenges to public key signature schemes as we know them today. LMS and XMSS are two hash based signature schemes that have been proposed in the IETF as quantum secure. Both schemes are based on well-studied hash trees, but their similarities and differences have not yet been discussed. In this work, we attempt to compare the two standards. We compare their security assumptions and quantify their signature and public key sizes. We also address the computation overhead they introduce. Our goal is to provide a clear understanding of the schemes' similarities and differences for implementers and protocol designers to be able to make a decision as to which standard to chose.
ePrint Report Removal Attacks on Logic Locking and Camouflaging Techniques Muhammad Yasin, Bodhisatwa Mazumdar, Ozugr Sinanoglu, Jeyavijayan Rajendran
With the adoption of a globalized and distributed IC design flow, IP piracy, reverse engineering, and counterfeiting threats are becoming more prevalent. Logic obfuscation techniques including logic locking and IC camouflaging have been developed to address these emergent challenges. A major challenge for logic locking and camouflaging techniques is to resist Boolean satisfiability (SAT) based attacks that can circumvent state-of-the-art solutions within minutes. Over the past year, multiple SAT attack resilient solutions such as Anti-SAT and AND-tree insertion (ATI) have been presented. In this paper, we perform a security analysis of these countermeasures and show that they leave structural traces behind in their attempts to thwart the SAT attack. We present two attacks, namely “signal probability skew” (SPS) attack and “sensitization guided SAT” (SGS) attack, that can break Anti-SAT and ATI, respectively, within minutes.
Event date: 12 April to 13 April 2018
Event Calendar CT-RSA 2018: CT-RSA 2018 San Francisco, United States of America, 16 April - 20 April 2018
Event date: 16 April to 20 April 2018