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

19:17 [Pub][ePrint] Filtered nonlinear cryptanalysis of reduced-round Serpent, and the Wrong-Key Randomization Hypothesis., by James McLaughlin and John A. Clark

  We present a deterministic algorithm to find nonlinear S-box approximations, and a new nonlinear cryptanalytic technique; the \"filtered\" nonlinear attack, which achieves the lowest data complexity of any known-plaintext attack on reduced-round Serpent so far. We demonstrate that the Wrong-Key Randomization Hypothesis is not entirely valid for attacks on reduced-round Serpent which rely on linear cryptanalysis or a variant thereof, and survey the effects of this on existing attacks (including existing nonlinear attacks) on 11 and 12-round Serpent.

19:17 [Pub][ePrint] Functional Encryption Supporting Recursive Languages, by Somindu C. Ramanna and Palash Sarkar

  We provide a construction for functional encryption over the set of recursive languages.

In this scheme, a secret key $\\sk_{\\mathcal{M}}$ encodes a halting double-stack deterministic pushdown

automaton (2DPDA) $\\mathcal{M}$ that accepts by final state. Encryption algorithm takes a message $m$

and a string $w$ as input and outputs a ciphertext $\\cipher$. A user possessing $\\sk_{\\mathcal{M}}$ can

decrypt $\\cipher$ only if $\\mathcal{M}$ accepts $w$. Halting 2DPDAs can simulate halting deterministic

Turing machines and hence our construction essentially covers all

recursive languages.

The construction is built upon Waters\' bilinear pairing-based functional encryption scheme

over regular languages. The main technical novelty is in handling stack contents and

$\\lambda$-transitions (i.e., transitions that do not advance the input pointer)

of the automata. This is reflected both in the construction and the security arguments.

The scheme is shown to be selectively secure based on the decision $\\ell$-expanded bilinear

Diffie-Hellman exponent assumption introduced by Waters.

19:17 [Pub][ePrint] Systematic Construction and Comprehensive Evaluation of the Kolmogorov-Smirnov Test based Side-Channel Distinguishers, by Hui Zhao, Yongbin Zhou, Francois-Xavier Standaert, Hailong Zhang

  Generic side-channel distinguishers aim at revealing the correct key embedded in cryptographic modules even when few assumptions can be made about their physical leakages. In this context, Kolmogorov-Smirnov Analysis (KSA) and Partial Kolmogorov-Smirnov analysis (PKS) were proposed respectively. Although both KSA and PKS are based on the Kolmogorov-Smirnov (KS) test, they really differ a lot from each other in terms of construction strategies. Inspired by this, we construct nine new variants by combining their strategies in a systematic way. Furthermore, we explore the effectiveness and efficiency of all these twelve KS test based distinguishers under various simulated scenarios in a univariate setting within a unified comparison framework, and also investigate how these distinguishers behave in practical scenarios. For these purposes, we perform a series of attacks against both simulated traces and real traces. Evaluation metrics such as Success Rate (SR) and Guessing Entropy (GE) are used to measure the efficiency of key recovery attacks in our evaluation. Our experimental results not only show how to choose the most suitable KS test based distinguisher in a particular scenario, but also clarify the practical meaning of all these KS test based distinguishers in practice.

19:17 [Pub][ePrint] Man-in-the-Middle Secure Authentication Schemes from LPN and Weak PRFs, by Vadim Lyubashevsky and Daniel Masny

  We show how to construct, from any weak pseudorandom function, a 3-round symmetric-key authentication protocol that is secure against man-in-the-middle attacks. The construction is very efficient, requiring both the secret key and communication size to be only 3n bits long. Our techniques also extend to certain classes of randomized weak-PRFs, chiefly among which are those based on the classical LPN problem and its more efficient variants such as Toeplitz-LPN and Ring-LPN. Building a man-in-the-middle secure authentication scheme from any weak-PRF resolves a problem left open by Dodis et al. (Eurocrypt 2012), while building a man-in-the-middle secure scheme based on any variant of the LPN problem solves the main open question in a long line of research aimed at constructing a practical light-weight authentication scheme based on learning problems, which began with the work of Hopper and Blum (Asiacrypt 2001).

19:17 [Pub][ePrint] On the security of a certificateless aggregate signature scheme, by Lin Cheng and Qiaoyan Wen and Zhengping Jin and Hua Zhang and Liming Zhou

  Aggregate signature can combinensignatures on nmessages fromnusers into a single short signature, and the resulting signature can convince the verifier that thenusers indeed signed

the ncorresponding messages. This feature makes aggregate signature very useful especially in environments with low bandwidth communication, low storage and low computability since it

greatly reduces the total signature length and verification cost. Recently, Xiong et al. presented an efficient certificateless aggregate signature scheme. They proved that their scheme is secure in a strengthened security model, where the \"malicious-but-passive\" KGC attack was considered. In this paper, we show that Xiong et al.\'s certificateless aggregate signature scheme is not secure

even in a weaker security model called \"honest-but-curious\" KGC attack model.

19:17 [Pub][ePrint] On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption, by Adriana Lopez-Alt and Eran Tromer and Vinod Vaikuntanathan

  We propose a new notion of secure multiparty computation aided by a computationally-powerful but untrusted \"cloud\" server. In this notion that we call

on-the-fly multiparty computation (MPC), the cloud can non-interactively perform arbitrary, dynamically chosen computations on data belonging to arbitrary sets of users chosen on-the-fly. All user\'s input data and intermediate results are protected from snooping by the cloud as well as other users.

This extends the standard notion of fully homomorphic encryption (FHE), where users can only enlist the cloud\'s help in evaluating functions on their own encrypted data.

In on-the-fly MPC, each user is involved only when initially uploading his (encrypted) data to the cloud, and in a final output decryption phase when outputs are revealed; the complexity of both is independent of the function being computed and the total number of users in the system. When users upload their data, they need not decide in advance which function will be computed, nor who they will compute with; they need only retroactively approve the eventually-chosen functions and on whose data the functions were evaluated.

This notion is qualitatively the best possible in minimizing interaction, since the users\' interaction in the decryption stage is inevitable: we show that removing it would imply generic program obfuscation and is thus impossible.

Our contributions are two-fold:

1. We show how on-the-fly MPC can be achieved using a new type of encryption scheme that we call multikey FHE, which is capable of operating on inputs encrypted under multiple, unrelated keys. A ciphertext resulting from a multikey evaluation can be jointly decrypted using the secret keys of all the users involved in the computation.

2. We construct a multikey FHE scheme based on NTRU, a very efficient public-key encryption scheme proposed in the 1990s. It was previously not known how to make NTRU fully homomorphic even for a single party. We view the construction of (multikey) FHE from NTRU encryption as a main contribution of independent interest. Although the transformation to a fully homomorphic system deteriorates the efficiency of NTRU somewhat, we believe that this system is a leading candidate for a practical FHE scheme.

18:44 [Job][New] Canada Excellence Research Chair in Security & Privacy, University of Waterloo, Canada

  We invite expressions of interest for the position of Canada Excellence Research Chair (CERC) in Security and Privacy for the New Digital Economy, to be held at the tenured full or associate professor level in the David R. Cheriton School of Computer Science at the University of Waterloo.

The CERC program awards world-class researchers up to $10 million over seven years to establish ambitious research programs at Canadian universities. Further details are offered at An overall package worth more than twice this amount will fund the CERC, additional faculty and staff, and their required infrastructure.

The applicant will be an outstanding researcher, well-recognized as exceptional within the subfield of security and privacy. It will also be essential for the candidate to demonstrate remarkable promise in leadership and in the mobilization of talents to deliver successful outcomes. In particular, we are looking for an individual who is expert in security solutions for networked and mobile environments with a critical appreciation for linking privacy to the required solutions. To promote the adoption of novel technological solutions, the CERC must also have an aptitude in working well with public policy experts.

To apply, send a cover letter and a curriculum vitae by e-mail at deanmath (at) or by regular mail.

Applications received by May 30, 2013 will receive full consideration. Selection of the candidate is subject to final oversight by the government\\\'s CERC Selection Committee.

The University of Waterloo encourages applications from all qualified individuals, including women, members of visible minorities, native people and persons with disabilities. We are proud to offer organizations for Women in Computer Science ( and Women in Mathematics ( as well as an AccessAbility Services Office for persons with disabiliti

13:17 [Pub][ePrint] Towards Provably Secure Software Attestation, by Frederik Armknecht and Ahmad-Reza Sadeghi and Steffen Schulz and Christian Wachsmann

  Software attestation has become a popular and challenging research topic at many established security conferences. It aims for verifying the software integrity of (typically) resource-constrained embedded devices. However, for practical reasons, software attestation cannot rely on stored cryptographic secrets or dedicated trusted hardware. Instead, it exploits side-channel information, such as the time that the underlying device needs for a specific computation. Unfortunately, traditional cryptographic solutions and arguments are not applicable in this setting, making new approaches for the design and analysis necessary. This is certainly one of the main reasons why the security properties and assumptions of software attestation have been only vaguely discussed and have never been formally treated, as it is common sense in modern cryptography. Thus, despite its popularity and its expected impact for practice, a sound approach for designing secure software attestation schemes is still an important open problem.

We introduce the first formal security framework for software attestation and formalize various system and design parameters. Moreover, we present a generic software attestation scheme that captures most existing schemes in the literature. Finally, we analyze its security within our framework, yielding sufficient conditions for provably secure software attestation schemes. We regard these results as a first step towards putting software attestation on a solid ground and as a starting point for further research.

13:17 [Pub][ePrint] Security of Quantum-Readout PUFs against quadrature based challenge estimation attacks, by Boris Skoric and Allard P. Mosk and Pepijn W.H. Pinkse

  The concept of quantum-secure readout of Physical Unclonable Functions (PUFs) has recently been realized experimentally in an optical PUF system. We analyze the security of this system under the strongest type of classical attack: the challenge estimation attack.

The adversary performs a measurement on the challenge quantum state in order to learn as much about it as he can. Using this knowledge he then tries to reconstruct the challenge and to emulate the PUF.

We consider quadrature measurements, which are the most informative practical measurements known to us.

We prove that even under this attack the expected number of photons

detected in the verification mechanism is approximately a factor $S+1$ too low; here $S$ is the Quantum Security Parameter, defined as the number of modes in the optical system divided by the number of photons in the challenge. The photon count allows for a reliable distinction between an authentic PUF and a challenge estimation attack.

13:17 [Pub][ePrint] Between a Rock and a Hard Place: Interpolating Between MPC and FHE, by Ashish Choudhury and Jake Loftus and Emmanuela Orsini and Arpita Patra and Nigel P. Smart

  We present a computationally secure MPC protocol for threshold

adversaries which is parametrized by a value L. When L=2 we obtain a classical form of MPC protocol in which interaction is required for multiplications, as L increases interaction is reduced in that one requires interaction only after computing a higher degree function. When L approaches infinity one obtains the FHE based protocol of Gentry, which requires no interaction. Thus one can trade communication for computation in a simple way.

Our protocol is based on an interactive protocol for ``bootstrapping\'\' a somewhat homomorphic encryption scheme. The key contribution is that our presented protocol is highly communication efficient enabling us to obtain reduced communication when compared to traditional MPC protocols for relatively small values of L.

13:17 [Pub][ePrint] Path-PIR: Lower Worst-Case Bounds by Combining ORAM and PIR, by Travis Mayberry and Erik-Oliver Blass and Agnes Chan

  Recent research results on \"bucketed\" ORAM reduce com- munication of N-capacity storage with blocks of length l bits down to poly-logarithmic complexity O(l · log^3 N ). The individual buckets, how- ever, are constructed using traditional ORAMs which have worst-case communication complexity being linear in their size. PIR protocols are able to provide better worst-case bounds, but have traditionally been less practical than ORAM due to the fact that they require O(N) computa- tion complexity on the server. This paper presents Path-PIR, a hybrid construction between PIR and ORAM that overcomes the individual weaknesses of each. Path-PIR\'s main idea is to replace the individual buckets in the ORAM construction by Shi et al. [15] with buckets backed by PIR. We show that this leads to substantially smaller data transfer costs for many databases of practical size and lower worst-case costs, O(l · log^2 (N) + log^3 (N)), than the existing construction. Additionally, the typically high computational cost of PIR is offset by the small size of the individual buckets. We also show that Path-PIR has very low latency, i.e., a low amount of data is required before a user receives the result of his data request (less than 10 times the block size). Using Amazon EC2, we demonstrate that monetary cost induced by the server\'s PIR computation are far outweighed by the savings in data transfer.