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

12:17 [Pub][ePrint] Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an FPGA Cluster, by Erich Wenger and Paul Wolfger

  Using FPGAs to compute the discrete logarithms of elliptic curves is a well known method. However, until now only CPU clusters succeeded in computing new elliptic curve discrete logarithm records. This work presents a high-speed FPGA implementation that was used to compute the discrete logarithm of a 113-bit Koblitz curve. The core of the design is a fully unrolled, highly pipelined, self-sufficient Pollard\'s rho iteration function. An 18-core Virtex-6 FPGA cluster computed the discrete logarithm of a 113-bit Koblitz curve in extrapolated 24 days. Until now, no attack on such a large Koblitz curve succeeded using so minimal resources or in such a short time frame.

12:17 [Pub][ePrint] On the Limits of Authenticated Key Exchange Security with an Application to Bad Randomness, by Michèle Feltz and Cas Cremers

  State-of-the-art authenticated key exchange (AKE) protocols are proven secure in game-based security models. These models have considerably evolved in strength from the original Bellare-Rogaway model. However, so far only informal impossibility results, which suggest that no protocol can be secure against stronger adversaries, have been sketched. At the same time, there are many different security models being used, all of which aim to model the strongest possible adversary. In this paper we provide the first systematic analysis of the limits of game-based security models. Our analysis reveals that different security goals can be achieved in different relevant classes of AKE protocols. From our formal impossibility results, we derive strong security models for these protocol classes and give protocols that are secure in them. In particular, we analyse the security of AKE protocols in the presence of adversaries who can perform attacks based on chosen randomness, in which the adversary controls the randomness used in protocol sessions. Protocols that do not modify memory shared among sessions, which we call stateless protocols, are insecure against chosen-randomness attacks. We propose novel stateful protocols that provide resilience even against this worst case randomness failure, thereby weakening the security assumptions required on the random number generator.

12:17 [Pub][ePrint] Compact VSS and Efficient Homomorphic UC Commitments, by Ivan Damgård and Bernardo David and Irene Giacomelli and Jesper Buus Nielsen

  We present a new compact verifiable secret sharing scheme, based on

this we present the first construction of a homomorphic UC commitment

scheme that requires only cheap symmetric cryptography, except for a

small number of seed OTs. To commit to a $k$-bit string, the amortized

communication cost is $O(k)$ bits. Assuming a sufficiently efficient

pseudorandom generator, the computational complexity is $O(k)$ for the

verifier and $O(k^{1+\\epsilon})$ for the committer (where $\\epsilon

12:17 [Pub][ePrint] On the Enumeration of Double-Base Chains with Applications to Elliptic Curve Cryptography, by Christophe Doche

  The Double-Base Number System (DBNS) uses two bases, $2$ and $3$, in order to represent any

integer $n$.

A Double-Base Chain (DBC) is a special case of a DBNS expansion. DBCs have been introduced to speed up

the scalar multiplication $[n]P$ on certain families of elliptic curves used in cryptography.

In this context, our contributions are twofold.

First, given integers $n$, $a$, and $b$, we outline a recursive algorithm

to compute the number of different DBCs with a \\lt{} dividing $2^a3^b$ and representing $n$. A


modification of the algorithm allows to

determine the number of DBCs with a specified length as well as the actual expansions. In turn, this

gives rise to a method to compute an optimal DBC representing $n$, i.e. an expansion with minimal


Our implementation is able to return an optimal expansion for most integers up to $2^{60}$ bits

in a few minutes.

Second, we introduce an original and potentially more efficient approach to compute a random

scalar multiplication $[n]P$, called controlled DBC. Instead of generating a random integer $n$

and then trying to find an

optimal, or at least a short DBC to represent it, we propose to directly generate $n$ as a

random DBC with a chosen length $\\ell$ and \\lt{} $2^a3^b$.

To inform the selection of those parameters, in particular $\\ell$, which drives the

trade-off between the

efficiency and the security of the

underlying cryptosystem, we

enumerate the total number of DBCs having a certain length $\\ell$ and a given

\\lt{} $2^a3^b$.

The comparison between this total number of DBCs and the total number of

integers that we wish to represent a priori provides some guidance regarding the selection of

suitable parameters. Our experiments indicate that the controlled DBC provides a speedup of at

least $6.98\\%$ and up to $8\\%$ for sizes from $192$ to $512$ bits. Experiments involve elliptic

curves defined over $\\F_p$, using the Inverted Edwards coordinate system and state of the art

scalar multiplication techniques.

12:17 [Pub][ePrint] Fully secure constrained pseudorandom functions using random oracles, by Dennis Hofheinz

  A constrained pseudorandom function (CPRF) PRF allows to derive constrained evaluation keys that only allow to evaluate PRF on a subset of inputs. CPRFs have only recently been introduced independently by three groups of researchers. However, somewhat curiously, all of them could only achieve a comparatively weak, selective-challenge form of security (except for small input spaces, very limited forms of constrained keys, or with superpolynomial security reductions).

In this paper, we construct the first fully secure CPRF without any of the above restrictions. Concretely, we support ``bit-fixing\'\' constrained keys that hardwire an arbitrary subset of the input bits to fixed values, we support exponentially large input spaces, and our security reduction is polynomial. We require very heavyweight tools: we assume multilinear maps, indistinguishability obfuscation, and our proof is in the random oracle model. Still, our analysis is far from tautological, and even with these strong building blocks, we need to develop additional techniques and tools.

As a simple application, we obtain the first adaptively secure non-interactive key exchange protocols for large user groups.

12:17 [Pub][ePrint] Beyond 2^{c/2} Security in Sponge-Based Authenticated Encryption Modes, by Philipp Jovanovic and Atul Luykx and Bart Mennink

  The Sponge function is known to achieve 2^{c/2} security, where c is its capacity. This bound was carried over to keyed variants of the function, such as SpongeWrap, to achieve a min{2^{c/2},2^kappa} security bound, with kappa the key length. Similarly, many CAESAR competition submissions are designed to comply with the classical 2^{c/2} security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of min{2^{b/2},2^c,2^kappa}, with b>c the permutation size, by proving that the CAESAR submission NORX achieves this bound. Furthermore, we show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. For instance, NORX64 can increase its rate and decrease its capacity with 128 bits and Ascon-128 can encrypt three times as fast, both without affecting the provable security level.

12:17 [Pub][ePrint] Optimal Contracts for Outsourced Computation, by Viet Pham and MHR. Khouzani and Carlos Cid

  While expensive cryptographically verifiable computation aims at defeating malicious agents, many civil purposes of outsourced computation tolerate a weaker notion of security, i.e., ``lazy-but-honest\'\' contractors. Targeting this type of agents, we develop optimal contracts for outsourcing of computational tasks via appropriate use of rewards, punishments, auditing rate, and ``redundancy\'\'. Our contracts provably minimize the expense of the outsourcer (principal) while guaranteeing correct computation. Furthermore, we incorporate practical restrictions of the maximum enforceable fine, limited and/or costly auditing, and bounded budget of the outsourcer. By examining the optimal contracts, we provide insights on how resources should be utilized when auditing capacity and enforceability are limited. Finally, we present a light-weight cryptographic implementation of the contracts and discuss a comparison across different implementations of auditing in outsourced computation.

11:42 [News] Fellows 2014

  The IACR Fellows 2014 have been announced:
  • Ran Canetti
  • Antoine Joux
  • Eyal Kushilevitz
  • Moti Yung

06:59 [Event][New] CryptoBG*2014: CryptoBG*2014: Cryptology and Cyber Resilience

  Submission: 15 June 2014
Notification: 25 June 2014
From July 20 to July 27
Location: Oriahovitza, Bulgaria
More Information:

06:59 [Event][New] UbiCrypt Summer School crypt@b-it 2014

  Submission: 1 July 2014
From July 28 to August 1
Location: Bochum, Germany
More Information:

12:17 [Pub][ePrint] New Results in the Linear Cryptanalysis of DES, by Igor Semaev

  Two open problems on using Matsui\'s Algorithm 2 with multiple linear approximations posed earlier by Biryukov, De Canni$\\grave{\\hbox{e}}$re and M. Quisquater at Crypto\'04 are solved in the present paper. That improves the linear cryptanalysis of 16-round DES reported by Matsui at Crypto\'94.