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).

18:17 [Pub][ePrint] Quantum Money from Hidden Subspaces, by Scott Aaronson and Paul Christiano

  Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that printed it, and (2) cryptographically secure, under a \"classical\" hardness assumption that has nothing to do with quantum money. Our scheme is based on hidden subspaces, encoded as the zero-sets of random multivariate polynomials. A main technical advance is to show that the \"black-box\" version of our scheme, where the polynomials are replaced by classical oracles, is unconditionally secure. Previously, such a result had only been known relative to a quantum oracle (and even there, the proof was never published). Even in Wiesner\'s original setting -- quantum money that can only be verified by the bank -- we are able to use our techniques to patch a major security hole in Wiesner\'s scheme. We give the first private-key quantum money scheme that allows unlimited verifications and that remains unconditionally secure, even if the counterfeiter can interact adaptively with the bank. Our money scheme is simpler than previous public-key quantum money schemes, including a knot-based scheme of Farhi et al. The verifier needs to perform only two tests, one in the standard basis and one in the Hadamard basis -- matching the original intuition for quantum money, based on the existence of complementary observables. Our security proofs use a new variant of Ambainis\'s quantum adversary method, and several other tools that might be of independent interest.

18:17 [Pub][ePrint] Attacking RSA-CRT Signatures with Faults on Montgomery Multiplication, by Pierre-Alain Fouque and Nicolas Guillermin and Delphine Leresteux and Mehdi Tibouchi and Jean-Christophe Zapalowicz

  In this paper, we present several efficient fault attacks against implementations of RSA-CRT signatures that use modular exponentiation algorithms based on Montgomery multiplication. They apply to any padding function, including randomized paddings, and as such are the

first fault attacks effective against RSA-PSS.

The new attacks work provided that a small register can be forced to either zero, or a constant value, or a value with zero high-order bits. We show that these models are quite realistic, as such faults can be achieved against many proposed hardware designs for RSA signatures.

18:17 [Pub][ePrint] Automatically Verified Mechanized Proof of One-Encryption Key Exchange, by Bruno Blanchet

  We present a mechanized proof of the password-based protocol One-Encryption Key Exchange (OEKE) using the computationally-sound protocol prover CryptoVerif. OEKE is a non-trivial protocol, and thus mechanizing its proof provides additional confidence that it is correct.

This case study was also an opportunity to implement several important extensions of CryptoVerif, useful for proving many other protocols. We have indeed extended CryptoVerif to support the computational Diffie-Hellman assumption. We have also added support for proofs that rely on Shoup\'s lemma and additional game transformations. In particular, it is now possible to insert case distinctions manually and to merge cases that no longer need to be distinguished. Eventually, some improvements have been added on the computation of the probability bounds for attacks, providing better reductions. In particular, we improve over the standard computation of probabilities when Shoup\'s lemma is used, which allows us to improve the bound given in a previous manual proof of OEKE, and to show that the adversary can test at most one password per session of the protocol.

In this paper, we present these extensions, with their application to the proof of OEKE. All steps of the proof, both automatic and manually guided, are verified by CryptoVerif.

18:17 [Pub][ePrint] Zero Knowledge with Rubik\'s Cubes, by Emmanuel VOLTE and Jacques PATARIN and Valérie NACHEF

  Since the invention of the Rubik\'s cube by Ern\\\"o~Rubik in $1974$, similar puzzles have been produced, with various number of faces or stickers. We can use these toys to define several problems in computer science, such as go from one state of the puzzle to another one. In this paper, we will classify some of these problems based on the classic Rubik\'s cube or on generalized Rubik\'s Cube. And we will see how we can use them in Zero Knowledge Authentication with a public key in order to achieve a given complexity against the best known attacks (for example $2^{80}$ computations). The efficiency of these schemes, and their possible connection with

NP-complete problems will also be discussed.

18:17 [Pub][ePrint] Optimal First-Order Masking with Linear and Non-Linear Bijections, by Houssem MAGHREBI, Claude CARLET, Sylvain GUILLEY and Jean-Luc DANGER

  Hardware devices can be protected against side-channel attacks by introducing one random mask per sensitive variable.

The computation throughout is unaltered if the shares (masked variable and mask) are processed concomitantly, in two distinct registers.

Nonetheless, this setup can be attacked by a zero-offset second-order CPA attack.

The countermeasure can be improved by manipulating the mask through a bijection $F$,

aimed at reducing the dependency between the shares.

Thus $d$th-order zero-offset attacks, that consist in applying CPA on the $d$th power of the centered side-channel traces,

can be thwarted for $d \\geq 2$ at no extra cost.

We denote by $n$ the size in bits of the shares and call $F$ the transformation function,

that is a bijection of $\\mathbb{F}_2^n$.

In this paper, we explore the functions $F$ that thwart zero-offset HO-CPA of maximal order $d$.

We mathematically demonstrate that optimal choices for $F$ relate to optimal binary codes (in the sense of communication theory).

First, we exhibit optimal linear $F$ functions.

Second, we note that for values of $n$ for which non-linear codes exist with better parameters than linear ones.

These results are exemplified in the case $n=8$, the optimal $F$ can be identified:

it is derived from the optimal rate~$1/2$ binary code of size $2n$, namely the Nordstrom-Robinson $(16, 256, 6)$ code.

This example provides explicitly with the optimal protection that limits to one mask of byte-oriented algorithms such as AES or AES-based SHA-3 candidates.

It protects against all zero-offset HO-CPA attacks of order $d \\leq 5$.

Eventually, the countermeasure is shown to be resilient to imperfect leakage models.

18:17 [Pub][ePrint] Improvements of Algebraic Attacks Based on Structured Gaussian Elimination, by Satrajit Ghosh and Abhijit Das

  Algebraic attacks are studied as a potential cryptanalytic procedure for various types of ciphers. The XL_SGE algorithm has been recently proposed to improve the complexity of the XL attack. XL_SGE uses structured Gaussian elimination (SGE) during the expansion phase of XL. In this paper, we establish that XL_SGE suffers from some serious drawbacks that impair the effectiveness of SGE-based reduction at all multiplication stages except the first. In order to avoid this problem, we propose several improvements of XL_SGE. Our modifications are based

upon partial monomial multiplication and handling of columns of weight two. Our modified algorithms have been experimentally verified to be substantially superior to XL_SGE.

18:17 [Pub][ePrint] Everlasting Quantum Security, by Unruh, Dominique

  A protocol has everlasting security if it is secure against

adversaries that are computationally unlimited after the protocol

execution. This models the fact that we cannot predict which

cryptographic schemes will be broken, say, several decades after the

protocol execution. In classical cryptography, everlasting security is

difficult to achieve: even using trusted setup like common reference

strings or signature cards, many tasks such as secure communication

and oblivious transfer cannot be achieved with everlasting security.

An analogous result in the quantum setting excludes protocols based on

common reference strings, but not protocols using a signature card. We

define a variant of the Universal Composability framework, everlasting

quantum-UC, and show that in this model, we can implement secure

communication and general two-party computation using a signature card

as trusted setup.

18:17 [Pub][ePrint] Eperio: Mitigating Technical Complexity in Cryptographic Election Verification, by Aleksander Essex and Jeremy Clark and Urs Hengartner and Carlisle Adams

  Cryptographic (or end-to-end) election verification is a promising approach to providing transparent elections in an age of electronic voting technology. In terms of execution time and software complexity however, the technical requirements for conducting a cryptographic election audit can be prohibitive. In an effort to reduce these requirements we present Eperio: a new, provably secure construction for providing a tally that can be efficiently verified using only a small set of primitives. We show how common-place utilities, like the use of file encryption, can further simplify the verification process for election auditors. Using Python, verification code can be expressed in 50 lines of code. Compared to other proposed proof-verification methods for end-to-end election audits, Eperio lowers the technical requirements in terms of execution time, data download times, and code size. As an interesting alternative, we explain how verification can be implemented using TrueCrypt and the built-in functions of a spreadsheet, making Eperio the first end-to-end system to not require special-purpose verification software.

18:17 [Pub][ePrint] Towards Billion-Gate Secure Computation with Malicious Adversaries, by Benjamin Kreuter and abhi shelat and Chih-hao Shen

  The goal of this paper is to assess the feasibility of two-party secure computation in the presence of a malicious adversary. Prior work has shown the feasibility of billion-gate circuits in the semi-honest model, but only the 35k-gate AES circuit in the malicious model, in part because security in the malicious model is much harder to achieve. We show that by incorporating the best known techniques and parallelizing almost all steps of the resulting protocol, evaluating billion-gate circuits is feasible in the malicious model. Our results are in the standard model (i.e., no common reference strings or PKIs) and, in contrast to prior work, we do not use the random oracle model which has well-established theoretical shortcomings.

18:17 [Pub][ePrint] Yet Another SHA-3 Round 3 FPGA Results Paper, by Brian Baldwin and William P. Marnane

  The NIST run SHA-3 competition is nearing completion. Currently in its final round, the five remaining competitors are still being examined in hardware, software and for security metrics in order to select a final winner. While there have been many area and speed results reported, one such metric that does not appear to be covered in very great detail is that of power and energy measurements on FPGA. This work attempts to add some new results to this section, namely, measured area, power, energy and iteration time results thereby giving NIST further metrics on which to base their selection decision.

18:17 [Pub][ePrint] Modular Design and Analysis Framework for Multi-Factor Authentication and Key Exchange, by Nils Fleischhacker and Mark Manulis and Amir Sadr-Azodi

  Multi-Factor Authentication (MFA), often coupled with Key Exchange (KE), offers very strong protection for secure communication and has been recommended by many major governmental and industrial bodies for the use in highly sensitive applications. Instantiations of the MFA concept vary in practice and in the research literature and various efforts in designing secure MFA protocols were unsuccessful.

This paper introduces a modular approach to the design and analysis of arbitrary MFAKE protocols, in form of an $(\\alpha,\\beta,\\gamma)$-MFAKE framework, that can accommodate multiple types and quantities of authentication factors, focusing on the three widely adopted categories that provide evidence of knowledge, possession, and physical presence. The framework comes with (i) a model for \\emph{generalized MFAKE} that implies many known flavors of single- and multi-factor Authenticated Key Exchange (AKE), and (ii) offers generic and modular constructions of secure MFAKE protocols that can be tailored to the needs of a particular application.

Our generic $\\mfake$ protocol is based on the new notion of \\emph{tag-based MFA} that in turn implies tag-based versions of many existing single-factor authentication schemes. We show examples and discuss generic ways to obtain tag-based flavors of password-based, public key-based, and biometric-based authentication protocols. By combining various tag-based single-factor authentication-only protocols, whose executions can be parallelized, with a single run of an Unauthenticated Key Exchange (UKE) we construct $\\mfake$ that is superior to a na{\\\"i}ve black-box combination of multiple single-factor AKE schemes.