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

00:17 [Pub][ePrint] Fast and compact elliptic-curve cryptography, by Mike Hamburg

Elliptic curve cryptosystems have improved greatly in speed over the past few years. In this paper we outline a new elliptic curve signature and key agreement implementation which achieves record speeds while remaining relatively compact. For example, on Intel Sandy Bridge, a curve with about $2^{250}$ points produces a signature in just under 60k clock cycles, verifies in under 169k clock cycles, and computes a Diffie-Hellman shared secret in under 153k clock cycles. Our implementation has a small footprint: the library is under 55kB. We also post competitive timings on ARM processors, verifying a signature in under 626k Tegra-2 cycles. We introduce faster field arithmetic, a new point compression algorithm, an improved fixed-base scalar multiplication algorithm and a new way to verify signatures without inversions or coordinate recovery. Some of these improvements should be applicable to other systems.

00:17 [Pub][ePrint] A mathematical problem for security analysis of hash functions and pseudorandom generators, by Koji Nuida and Takuro Abe and Shizuo Kaji and Toshiaki Maeno and Yasuhide Numata

  In this paper, we specify a class of mathematical problems, which we refer to as ``Function Density Problems\'\' (FDPs, in short), and point out novel connections of FDPs to the following two cryptographic topics; theoretical security evaluations of keyless hash functions (such as SHA-1), and constructions of provably secure pseudorandom generators (PRGs) with some enhanced security property introduced by Dubrov and Ishai [STOC 2006]. Our argument aims at proposing new theoretical frameworks for these topics (especially for the former) based on FDPs, rather than providing some concrete and practical results on the topics. We also give some examples of mathematical discussions on FDPs, which would be of independent interest from mathematical viewpoints. Finally, we discuss possible directions of future research on other cryptographic applications of FDPs and on mathematical studies on FDPs themselves.

00:17 [Pub][ePrint] Tightly Secure Signatures and Public-Key Encryption, by Dennis Hofheinz and Tibor Jager

  We construct the first public-key encryption scheme whose chosen-ciphertext (i.e., IND-CCA) security can be proved under a standard assumption and does not degrade in either the number of users or the number of ciphertexts. In particular, our scheme can be safely deployed in unknown settings in which no a-priori bound on the number of encryptions and/or users is known.

As a central technical building block, we devise the first structure-preserving signature scheme with a tight security reduction. (This signature scheme may be of independent interest.) Combining this scheme with Groth-Sahai proofs yields a tightly simulation-sound non-interactive zero-knowledge proof system for group equations. If we use this proof system in the Naor-Yung double encryption scheme, we obtain a tightly IND-CCA secure public-key encryption scheme from the Decision Linear assumption.

We point out that our techniques are not specific to public-key encryption security. Rather, we view our signature scheme and proof system as general building blocks that can help to achieve a tight security reduction.

00:17 [Pub][ePrint] Cryptanalysis of a Provably Secure Gateway-Oriented Password-Based Authenticated Key Exchange Protocol, by Debiao He

  Recently, Chien et al. proposed a gateway-oriented password-based authenticated key exchange (GPAKE) protocol, through which a client and a gateway could generate a session key for future communication with the help of an authentication server. They also demonstrated that their scheme is provably secure in a formal model. However, in this letter, we will show that Chien et al.\'s protocol is vulnerable to the off-line password guessing attack. To overcome the weakness, we also propose an efficient countermeasure.

00:17 [Pub][ePrint] An anonymous proxy signature scheme without random oracles, by Rahim Toluee and Maryam Rajabzadeh Asaar and Mahmoud Salmasizadeh

  The concept of proxy signature was introduced in 1996, up to now many proxy signature schemes have been proposed. In order to protect the proxy signer\'s privacy, the concept of anonymous proxy signature, which is also called proxy ring signature, was introduced in 2003. Some anonymous proxy signature schemes, which are provable secure in the random oracle model, have been proposed. However, provable security in the random oracle model is doubtful when the random oracles are instantiated with hash functions in their implementation. Hence, we propose the first secure anonymous proxy signature scheme without random oracles.

00:17 [Pub][ePrint] Generation of Nonlinear Feedback Shift Registers with special-purpose hardware, by Tomasz Rachwalik and Janusz Szmidt and Robert Wicik, and Janusz Zablocki

  The nonlinear feedback shift registers (NLFSR) are used to construct pseudorandom generators for stream ciphers. Their theory is not so complete as that of the linear feedback shift registers (LFSR). In general, it is not known how to construct NLFSRs with maximum period. The direct method is to search for such registers with suitable properties. We used the implementation of NLFSRs in Field Programmable Gate Arrays (FPGA) to perform a corresponding search. We also investigated local statistical properties of the binary sequences ganerated by NLFSRs of order 25 and 27.

21:17 [Pub][ePrint] New Transference Theorems on Lattices Possessing n^\\epsilon-unique Shortest Vectors, by Wei Wei and Chengliang Tian and Xiaoyun Wang

  We prove three optimal transference theorems on lattices possessing $n^{\\epsilon}$-unique shortest vectors which relate to the successive minima, the covering radius and the minimal length of

generating vectors respectively. The theorems result in reductions

between GapSVP$_{\\gamma\'}$ and GapSIVP$_\\gamma$ for this class of

lattices. Furthermore, we prove a new transference theorem giving an

optimal lower bound relating the successive minima of a lattice with

its dual. As an application, we compare the respective advantages of

current upper bounds on the smoothing parameter of discrete Gaussian

measures over lattices and show a more appropriate bound for lattices whose duals possess $\\sqrt{n}$-unique shortest vectors.

21:17 [Pub][ePrint] Two grumpy giants and a baby, by Daniel J. Bernstein and Tanja Lange

  Pollard\'s rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups.

This paper presents two reasons that Pollard\'s rho algorithm

is farther from optimality than generally believed.

First, ``higher-degree local anti-collisions\'\'

make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic.

Second, even a truly random walk is suboptimal,

because it suffers from ``global anti-collisions\'\' that can at least partially be avoided.

For example, after (1.5+o(1))\\sqrt(l) additions in a group of order l (without fast negation),

the baby-step-giant-step method has probability 0.5625+o(1)

of finding a uniform random discrete logarithm;

a truly random walk would have probability 0.6753\\ldots+o(1);

and this paper\'s new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1).

21:17 [Pub][ePrint] Broadcast-enhanced Key Predistribution Schemes, by Michelle Kendall and Keith M. Martin and Siaw-Lynn Ng and Maura B. Paterson and Douglas R. Stinson

  We present a formalisation of a category of schemes which we call \\emph{Broadcast-enhanced Key Predistribution Schemes}.

These schemes can be used instead of a key predistribution scheme in any network which has access to a trusted base station and broadcast channel.

In such networks, broadcast-enhanced key predistribution schemes can provide advantages over key predistribution schemes including flexibility and more efficient revocation.

There are many possible applications and ways to implement broadcast-enhanced key predistribution schemes, and we propose a framework for describing, comparing and analysing them.

In their paper `From key predistribution to key redistribution\', Cicho\\\'{n}, Go{\\l}\\c{e}biewski and Kuty{\\l}owski propose a scheme for `redistributing\' keys to a wireless sensor network using a broadcast channel after an initial key predistribution.

We classify this as a broadcast-enhanced key predistribution scheme and analyse it in that context.

We provide simpler proofs of some results from their paper, give a precise analysis of the resilience of their scheme, and discuss modifications based on defining a suitable keyring intersection threshold.

In the latter half of the paper we suggest two particular scenarios where broadcast-enhanced key predistribution schemes may be particularly desirable and the relevant design goals to prioritise in each case.

For each scenario we propose a suitable family of broadcast-enhanced key predistribution schemes and our analysis demonstrates their effectiveness in achieving their aims in resource-constrained networks.

21:17 [Pub][ePrint] In the blink of an eye: There goes your AES key, by Sergei Skorobogatov and Christopher Woods

  This paper is a short summary of a real world AES key extraction performed on a military grade FPGA marketed as \'virtually unbreakable\' and \'highly secure\'. We demonstrated that it is possible to extract the AES key from the Actel/Microsemi ProASIC3 chip in a time of 0.01 seconds using a new side-channel analysis technique called Pipeline Emission Analysis (PEA). This new technique does not introduce a new form of side-channel attacks (SCA), it introduces a substantially improved method of waveform analysis over conventional attack technology. It could be used to improve upon the speed at which all SCA can be performed, on any device and especially against devices previously thought to be unfeasible to break because of the time and equipment cost. Possessing the AES key for the ProASIC3 would allow an attacker to decrypt the bitstream or authenticate himself as a legitimate user and extract the bitstream from the device where no read back facility exists. This means the device is wide open to intellectual property theft, fraud and reverse engineering of the design to allow the introduction of a backdoor or Trojan. We show that with a very low cost hardware setup made with parts obtained from a local electronics distributor you can improve upon existing SCA up to a factor of x1,000,000 in time and at a fraction of the cost of existing SCA equipment.

21:17 [Pub][ePrint] Tamper and Leakage Resilience in the Split-State Model, by Feng-Hao Liu and Anna Lysyanskaya

  It is notoriously difficult to create hardware that is immune from side channel and tampering attacks. A lot of recent literature, therefore, has instead considered \\emph{algorithmic} defenses from such attacks.

In this paper, we show how to algorithmically secure any cryptographic functionality from continual split-state leakage and tampering attacks. A split-state attack on cryptographic hardware is one that targets separate parts of the hardware separately. Our construction does not require the hardware to have access to randomness. In contrast, prior work on protecting from continual combined leakage and tampering required true randomness for each update. Our construction is in the common reference string (CRS) model; the CRS must be hard-wired into the device. We note that prior negative results show that it is impossible to algorithmically secure a cryptographic functionality against a combination of arbitrary continual leakage and tampering attacks without true randomness; therefore restricting our attention to the split-state model is justified.

Our construction is simple and modular, and relies on a new construction, in the CRS model, of non-malleable codes with respect to split-state tampering functions, which may be of independent interest.