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

15:17 [Pub][ePrint] Polynomial Spaces: A New Framework for Composite-to-Prime-Order Transformations, by Gottfried Herold and Julia Hesse and Dennis Hofheinz and Carla Ràfols and Andy Rupp

  At Eurocrypt 2010, Freeman presented a framework to convert cryptosystems based on composite-order groups into ones that use prime-order groups. Such a transformation is interesting not only from a conceptual point of view, but also since for relevant parameters, operations in prime-order groups are faster than composite-order operations by an order of magnitude. Since Freeman\'s work, several other works have shown improvements, but also lower bounds on the efficiency of such conversions.

In this work, we present a new framework for composite-to-prime-order conversions. Our framework is in the spirit of Freeman\'s work; however, we develop a different, ``polynomial\'\' view of his approach, and revisit several of his design decisions. This eventually leads to significant efficiency improvements, and enables us to circumvent previous lower bounds. Specifically, we show how to implement Groth-Sahai proofs in a prime-order environment (with a symmetric pairing) almost twice as efficiently as the state of the art.

We also show that our new conversions are optimal in a very broad sense. Besides, our conversions also apply in settings with a multilinear map, and can be instantiated from a variety of computational assumptions (including, e.g., the $k$-linear assumption).

12:59 [News] Calls for IACR Cryptology School Proposals


Starting in 2014, IACR will sponsor a small number of Cryptology Schools providing intensive training on clearly identified topics in cryptology. The aim of this program is to develop awareness and increased capacity for research in cryptology.

A Cryptology School is typically held full-time for 4-5 days of intensive learning and constitutes an efficient way to provide high-quality training for graduate students, as well as for professionals. Attendance should be open to anyone who is interested and qualified. In order to facilitate learning, a school is usually taught by a few domain experts with a focus on educating the audience rather than impressing with results. In line with the mission of IACR, a Cryptology School should enable the audience to advance the theory and practice of cryptology and related fields.

There are two rounds of submissions every year. The submission deadlines are:

  • December 31st of year X-1: For schools that take place between March of year X and February of year X + 1.
  • June 30th of year X: For schools that take place between September of year X and August of year X + 1.
Submissions must be sent by email to schools /at/

For more information about this new program and how to prepare a proposal, please refer to

12:17 [Pub][ePrint] RPKI vs ROVER: Comparing the Risks of BGP Security Solutions, by Aanchal Malhotra and Sharon Goldberg

  Route Origin Verification (ROVER), a mechanism for securing interdomain routing with BGP, is a proposed alternative to the Resource Public Key Infrastructure (RPKI). While the RPKI requires the design and deployment of a completely new security infrastructure, ROVER leverages existing reverse DNS and DNSSEC deployments. Both ROVER and RPKI are based on a hierarchy of authorities that are trusted to provide information about the routing system.

It has been argued recently that misconfigurations or compromises of the RPKI\'s trusted authorities can present new risks to the routing system. Meanwhile, the advocates of ROVER claim that it provides a \"fail-safe\" approach, where the Internet will continue to work as it is even when ROVER fails. This poster therefore compares the impact of ROVER failures to those of the RPKI.

12:08 [Event][New] ICMC 2015: The second International Conference on Mathematics and Computing

  Submission: 16 July 2014
From January 5 to January 10
Location: Haldia, India
More Information:

06:17 [Pub][ePrint] Improved Generic Attacks Against Hash-based MACs and HAIFA, by Itai Dinur and Gaëtan Leurent

  The security of HMAC (and similar hash-based MACs) against

state-recovery and universal forgery attacks was very recently shown to

be suboptimal, following a series of surprising results by Leurent et

al. and Peyrin et al. These results have shown that such powerful

attacks require much less than $2^{\\ell}$ computations, contradicting

the common belief (where $\\ell$ denotes the internal state size). In

this work, we revisit and extend these results, with a focus on

properties of concrete hash functions such as a limited message length,

and special iteration modes.

We begin by devising the first state-recovery attack on HMAC with a

HAIFA hash function (using a block counter in every compression function

call), with complexity $2^{4\\ell/5}$. Then, we describe improved

trade-offs between the message length and the complexity of a

state-recovery attack on HMAC. Consequently, we obtain improved attacks

on several HMAC constructions used in practice, in which the the hash

functions limit the maximal message length (e.g., SHA-1 and SHA-2).

Finally, we present the first universal forgery attacks, which can be

applied with short message queries to the MAC oracle. In particular, we

devise the first universal forgery attacks applicable to SHA-1 and


06:17 [Pub][ePrint] Secure Outsourced Computation of the Characteristic Polynomial and Eigenvalues of Matrix, by Xing Hu and Chunming Tang

  Linear algebra plays an important role in computer science, especially in cryptography.Numerous cryptog-raphic protocols, scientific computations, and numerical computations are based on linear algebra. Many linear algebra tasks can be reduced to some core problems, such as matrix multiplication, determinant of matrix and the characteristic polynomial of matrix. However, it is difficult to execute these tasks independently for client whose computation abilities are weaker than polynomial-time computational ability. Cloud Computing is a novel economical paradigm which provides powerful computational resources that enables resources-constrained client to outsource their mass computing tasks to the cloud.

In this paper, we propose a new verifiable and secure outsourcing protocol for the problem of computing the characteristic polynomial and eigenvalues of matrix. These protocols are not only efficient and secure, but also unnecessary for any cryptographic assumption.

06:17 [Pub][ePrint] Minimizing the Two-Round Even-Mansour Cipher, by Shan Chen and Rodolphe Lampe and Jooyoung Lee and Yannick Seurin and John P. Steinberger

  The $r$-round (iterated) \\emph{Even-Mansour cipher} (also known as \\emph{key-alternating cipher}) defines a block cipher from $r$ fixed public $n$-bit permutations $P_1,\\ldots,P_r$ as follows: given a sequence of $n$-bit round keys $k_0,\\ldots,k_r$, an $n$-bit plaintext $x$ is encrypted by xoring round key $k_0$, applying permutation $P_1$, xoring round key $k_1$, etc. The (strong) pseudorandomness of this construction in the random permutation model (i.e., when the permutations $P_1,\\ldots,P_r$ are public random permutation oracles that the adversary can query in a black-box way) was studied in a number of recent papers, culminating with the work of Chen and Steinberger (EUROCRYPT~2014), who proved that the $r$-round Even-Mansour cipher is indistinguishable from a truly random permutation up to $O(2^{\\frac{rn}{r+1}})$ queries of any adaptive adversary (which is an optimal security bound since it matches a simple distinguishing attack). All results in this entire line of work share the common restriction that they only hold under the assumption that \\emph{the round keys $k_0,\\ldots,k_r$ and the permutations $P_1,\\ldots,P_r$ are independent}. In particular, for two rounds, the current state of knowledge is that the block cipher $E(x)=k_2\\oplus P_2(k_1\\oplus P_1(k_0\\oplus x))$ is provably secure up to $O(2^{2n/3})$ queries of the adversary, when $k_0$, $k_1$, and $k_2$ are three independent $n$-bit keys, and $P_1$ and $P_2$ are two independent random $n$-bit permutations. In this paper, we ask whether one can obtain a similar bound for the two-round Even-Mansour cipher \\emph{from just one $n$-bit key and one $n$-bit permutation}. Our answer is positive: when the three $n$-bit round keys $k_0$, $k_1$, and $k_2$ are adequately derived from an $n$-bit master key $k$, and the same permutation $P$ is used in place of $P_1$ and $P_2$, we prove a qualitatively similar $\\tilde{O}(2^{2n/3})$ security bound (in the random permutation model). To the best of our knowledge, this is the first ``beyond the birthday bound\'\' security result for AES-like ciphers that does not assume independent round keys.

06:17 [Pub][ePrint] Just a Little Bit More, by Joop van de Pol and Nigel P. Smart and Yuval Yarom

  We extend the FLUSH+RELOAD side-channel attack of Benger et al. to extract a significantly larger number of bits of information per observed signature when using OpenSSL. This means that by observing only 25 signatures, we can recover secret keys of the secp256k1 curve, used in the Bitcoin protocol, with a probability greater than 50 percent. This is an order of magnitude improvement over the previously best known result.

The new method of attack exploits two points: Unlike previous partial disclosure attacks we utilize all information obtained and not just that in the least significant or most significant bits, this is enabled by a property of the \"standard\" curves choice of group order which enables extra bits of information to be extracted. Furthermore, whereas previous works require direct information on ephemeral key bits, our attack utilizes the indirect information from the wNAF double and add chain.

06:17 [Pub][ePrint] Wait a minute! A fast, Cross-VM attack on AES, by Gorka Irazoqui and Mehmet Sinan Inci and Thomas Eisenbarth and Berk Sunar

  In cloud computing, efficiencies are reaped by resource sharing such as co-location of computation and deduplication of data. This work exploits resource sharing in virtualization software to build a powerful cache-based attack on AES. We demonstrate the vulnerability by mounting Cross-VM Flush+Reload cache attacks in VMware VMs to recover the AES keys of OpenSSL 1.0.1 running inside the victim VM. Furthermore, the attack works in a realistic setting where different VMs are located on separate cores. The modified flush+reload attack we present, takes only in the order of seconds to minutes to succeed in a cross-VM setting. Therefore long term co-location, as required by other fine grain attacks in the literature, are not needed. The results of this study show that there is a great security risk to OpenSSL AES implementation running on VMware cloud services when the deduplication is not disabled.

06:17 [Pub][ePrint] Synthesis of Fault Attacks on Cryptographic Implementations, by Gilles Barthe and Francois Dupressoir and Pierre-Alain Fouque and Benjamin Gregoire and Jean-Christophe Zapalowicz

  Fault attacks are active attacks in which an adversary with physical

access to a cryptographic device, for instance a smartcard, tampers

with the execution of an algorithm to retrieve secret material. Since

the seminal Bellcore attack on RSA signatures, there has been

extensive work to discover new fault attacks against cryptographic

schemes, and to develop countermeasures against such

attacks. Originally focused on high-level algorithmic descriptions,

these works increasingly focus on concrete implementations. While

lowering the abstraction level leads to new fault attacks, it also

makes their discovery significantly more challenging. In order to face

this trend, it is therefore desirable to develop principled,

tool-supported approaches that allow a systematic analysis of the

security of cryptographic implementations against fault attacks.

We propose, implement, and evaluate a new approach for finding fault

attacks against cryptographic implementations. Our approach is based

on identifying implementation-independent mathematical properties we

call fault conditions. We choose them so that it is possible to

recover secret data purely by computing on sufficiently many data

points that satisfy a fault condition. Fault conditions capture the

essence of a large number of attacks from the literature, including

lattice-based attacks on RSA. Moreover, they provide a basis for

discovering automatically new attacks: using fault conditions, we

specify the problem of finding faulted implementations as a program

synthesis problem. Using a specialized form of program synthesis, we

discover multiple faulted implementations on RSA and ECDSA that

realize the fault conditions, and hence lead to fault attacks. Several

of the attacks found by our tool are new, and of independent interest.

06:17 [Pub][ePrint] Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences, by Jingguo Bi and Jean-S\\\'ebastien Coron and Jean-Charles Faug\\`ere and Phong Q. Nguyen and Gu\\\'ena\\\"

  In a seminal work at EUROCRYPT \'96, Coppersmith showed how to find

all small roots of a univariate polynomial congruence in polynomial

time: this has found many applications in public-key cryptanalysis

and in a few security proofs. However, the running time of the

algorithm is a high-degree polynomial, which limits experiments: the

bottleneck is an LLL reduction of a high-dimensional matrix with

extra-large coefficients. We present in this paper the first

significant speedups over Coppersmith\'s algorithm. The first

speedup is based on a special property of the matrices used by

Coppersmith\'s algorithm, which allows us to provably speed up the

LLL reduction by rounding, and which can also be used to improve

the complexity analysis of Coppersmith\'s original algorithm.

The exact speedup depends on the LLL algorithm used: for instance,

the speedup is asymptotically quadratic in the bit-size of the

small-root bound if one uses the Nguyen-Stehl\\\'e {\\Ltwo}

algorithm. The second speedup is heuristic and applies whenever

one wants to enlarge the root size of Coppersmith\'s algorithm by

exhaustive search. Instead of performing several LLL reductions

independently, we exploit hidden relationships between these

matrices so that the LLL reductions can be somewhat chained to

decrease the global running time. When both speedups are combined,

the new algorithm is in practice hundreds of times faster for

typical parameters.