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

09:17 [Pub][ePrint] Improving GGH Public Key Scheme Using Low Density Lattice Codes, by Reza Hooshmand, Taraneh Eghlidos and Mohammad Reza Aref

  Goldreich-Goldwasser-Halevi (GGH) public key cryptosystem is an instance of lattice-based cryptosystems whose security is based on the hardness of lattice problems. In fact, GGH cryptosystem is the lattice version of the first code-based cryptosystem, proposed by McEliece. However, it has a number of drawbacks such as; large public key length and low security level. On the other hand, Low Density Lattice Codes (LDLCs) are the practical classes of linear codes which can achieve capacity on the additive white Gaussian noise (AWGN) channel with low complexity decoding algorithm. This paper introduces a public key cryptosystem based on LDLCs to withdraw the drawbacks of GGH cryptosystem. To reduce the key length, we employ the generator matrix of the used LDLC in Hermite normal form (HNF) as the public key. Also, by exploiting the linear decoding complexity of the used LDLC, the decryption complexity is decreased compared to GGH cryptosystem. These increased efficiencies allow us to use the bigger values of security parameters. Moreover, we exploit the special Gaussian vector whose variance is upper bounded by the Poltyrev limit as the perturbation vector. These techniques can resist the proposed scheme against the most efficient attacks to the GGH-like cryptosystems.

09:17 [Pub][ePrint] W-SPS: Designing a Wide-Area Secure Positioning System, by Der-Yeuan Yu and Aanjhan Ranganathan and Ramya Jayaram Masti and Claudio Soriente and Srdjan Capkun

  Motivated by the security and functional limitations of satellite positioning systems, we explore a design of a Wide-Area Secure Positioning System. The main goals of this system are strong spoofing resilience, location verification, and privacy. We propose a realization of a Wide-Area Secure Positioning System and show that this solution is viable and can fulfill our defined security goals. Specifically, our system is composed of a secure positioning infrastructure to obtain reliable location information of an entity and a location verification architecture that allows others to be convinced of certain location properties of such an entity. The proposed system enables the verification of location claims in a privacy-preserving manner, thus enhancing existing security solutions and supporting future location-based applications.

09:17 [Pub][ePrint] A Related-Key Chosen-IV Distinguishing Attack on Full Sprout Stream Cipher, by Yonglin Hao

  Sprout is a new lightweight stream cipher proposed at FSE 2015.

According to its designers, Sprout can resist time-memory-data trade-off (TMDTO) attacks with small internal state size.

However, we find a weakness in the updating functions of Sprout and propose a related-key chosen-IV distinguishing attack on full Sprout.

Our attack enable the adversary to distinguish detect non-randomness on full 320-round Sprout with a practical complexity (no more than $2^{20}$ key-IV pairs).

09:17 [Pub][ePrint] Cryptanalysis of Full Sprout, by Virginie Lallemand and Mar\\\'ia Naya-Plasencia

  A new method for reducing the internal state size of stream cipher registers has been proposed in FSE 2015, allowing to reduce the area in hardware implementations. Along with it, an instantiated proposal of a cipher was also proposed: Sprout. In this paper, we analyze the security of Sprout, and we propose an attack that recovers the whole key more than $2^{10}$ times faster than exhaustive search and has very low data complexity. The attack can be seen as a divide-and-conquer evolved technique, that exploits the non-linear influence of the key bits on the update function. We have implemented the attack on a toy version of Sprout, that conserves the main properties exploited in the attack. The attack completely matches the expected complexities predicted by our theoretical cryptanalysis, which proves its validity. We believe that our attack raises legitimate questions regarding the security of the proposed design method.

09:17 [Pub][ePrint] Computational Election Verifiability: Definitions and an Analysis of Helios and JCJ, by Ben Smyth and Steven Frink and Michael R. Clarkson

  Definitions of election verifiability in the computational model of cryptography are proposed. The definitions formalize notions of voters verifying their own votes, auditors verifying the tally of votes, and auditors verifying that only eligible voters vote. The Helios (Adida et al., 2009) and JCJ (Juels et al., 2010) election schemes are shown to satisfy these definitions. Two previous definitions (Juels et al., 2010; Cortier et al., 2014) are shown to permit election schemes vulnerable to attacks, whereas the new definitions prohibit those schemes.

16:45 [Event][New] SPACE 2015: Intl. Conf. on Security, Privacy, and Applied Cryptography Engineering

  Submission: 24 May 2015
Notification: 28 June 2015
From October 3 to October 7
Location: Jaipur, India
More Information:

12:17 [Pub][ePrint] Secure Physical Computation using Disposable Circuits, by Ben Fisch and Daniel Freund and Moni Naor

  In a secure physical computation, a set of parties each have physical inputs and jointly compute a function of their inputs in a way that reveals no information to any party except for the output of the function. Recent work in CRYPTO\'14 presented examples of physical zero-knowledge proofs of physical properties, a special case of secure physical two-party computation in which one party has a physical input and the second party verifies a boolean function of that input. While the work suggested a general framework for modeling and analyzing physical zero-knowledge protocols, it did not provide a general theory of how to prove any physical property with zero-knowledge. This paper takes an orthogonal approach using disposable circuits (DC)--cheap hardware tokens that can be completely destroyed after a computation--an extension of the familiar tamper-proof token model. In the DC model, we demonstrate that two parties can compute any function of their physical inputs in a way that leaks at most 1 bit of additional information to either party. Moreover, our result generalizes to any multi-party physical computation. Formally, our protocols achieve unconditional UC-security with input-dependent abort.

12:17 [Pub][ePrint] Tradeoff Cryptanalysis of Memory-Hard Functions, by Alex Biryukov and Dmitry Khovratovich

  We explore time-memory and other tradeoffs for memory-hard functions, which are supposed to impose significant computational and time penalties if less memory is used than intended. We analyze two schemes: Catena, which has been presented at Asiacrypt 2014, and Lyra2, the fastest finalist of the Password Hashing Competition (PHC).

We demonstrate that Catena\'s proof of tradeoff resilience is flawed, and attack it with a novel \\emph{precomputation tradeoff}. We show that using $M^{2/3}$ memory instead of $M$ we may have no time penalties. We further generalize our method for a wide class of schemes with predictable memory access.

For Lyra2, which addresses memory unpredictability (depending on the input), we develop a novel \\emph{ranking tradeoff} and show how to decrease the time-memory and the time-area product by significant factors. We also generalize the ranking method for a wide class of schemes with unpredictable memory access.

12:17 [Pub][ePrint] Leakage-Resilient Cryptography with Key Derived from Sensitive Data, by Konrad Durnoga and Tomasz Kazana and Michał Zając and Maciej Zdanowicz

  In this paper we address the problem of large space consumption for protocols in the Bounded Retrieval Model (BRM), which require users to store large secret keys subject to adversarial leakage.

We propose a method to derive keys for such protocols on-the-fly from weakly random private data (like text documents or photos, users keep on their disks anyway for non-cryptographic purposes) in such a way that no extra storage is needed. We prove that any leakage-resilient protocol (belonging to a certain, arguably quite broad class) when run with a key obtained this way retains a similar level of security as the original protocol had. Additionally, we guarantee privacy of the data the actual keys are derived from. That is, an adversary can hardly gain any knowledge about the private data except that he could otherwise obtain via leakage. Our reduction works in the Random Oracle model.

As an important tool in the proof we use a newly established bound for min-entropy, which can be of independent interest. It may be viewed as an analogue of the chain rule -- a weaker form of the well-known formula $\\mathbf{H}(X \\vert Y) = \\mathbf{H}(X, Y) - \\mathbf{H}(Y)$ for random variables $X$, $Y$, and Shannon entropy, which our result originates from. For min-entropy only a much more limited version of this relation is known to hold. Namely, the min-entropy of $X$ may decrease by up to the bitlength of $Y$ when $X$ is conditioned on $Y$, in short: $\\widetilde{\\mathbf{H}(X \\vert Y) \\geq \\mathbf{H}_\\infty(X) - \\lvert Y\\rvert$.

In many cases this inequality does not offer tight bounds, and such significant entropy loss makes it inadequate for our particular application. In the quasi chain rule we propose, we inject some carefully crafted side information (spoiling knowledge) to show that with large probability the average min-entropy of $X$ conditioned on both: $Y$ and this side information can be almost lower bounded by the min-entropy of $(X, Y)$ decreased by the min-entropy of $Y$ conditioned on the side information.

22:31 [Job][New] Ph.D. student - PUF design and security, Laboratoire Hubert Curien, University of Lyon, Saint-Etienne, France

  The main objective of the research in the group Applied Cryptography & Telecom is to propose efficient and robust hardware architectures aimed at applied cryptography and telecom that are resistant to passive and active cryptographic attacks. Currently, the central theme of this research consists in designing architectures for Secure Embedded Systems implemented in logic devices such as FPGAs and ASICs. More information on

The PhD thesis will take part of the European H2020 Project HECTOR (Hardware Enabled CrypTOgraphy and Randomness) aims at bridging the gap between the mathematics of cryptography with the reality of hardware implementations. HECTOR consortium: Technickon (Austria), KU Leuven (Belgium), Univ. Jean Monnet St-Etienne (France), TU Graz (Austria), THALES Comm. & Security SAS (France), STMicroelectronics Rousset SAS (France), STMicroelectronics SRL (Italia), Brighstsight (Netherlands), Micronic (Slovakia).

Objective of this thesis is to propose a set of tools that would allow simplifying physical unclonable functions (PUFs) design and security assessment.

We are looking for candidates with an outstanding Master in electrical engineering. Strong knowledge in VLSI design, FPGA & ASIC design are required. A first experience with PUF or TRNG design would be also appreciated. Notions of stochastic modelling will be a bonus. Skills in oral presentation and scientific writing in English are required (French is not required but recommended).

The PhD position will start before October 2015, it is funded for 36 months.

21:17 [Pub][ePrint] Key Homomorphic PRFs and Their Applications, by Dan Boneh and Kevin Lewi and Hart Montgomery and Ananth Raghunathan

  A pseudorandom function F : K x X -> Y is said to be key homomorphic if given F(k1, x) and F(k2, x) there is an efficient algorithm to compute F(k1 xor k2, x), where xor denotes a group

operation on k1 and k2 such as xor. Key homomorphic PRFs are natural objects to study and have a number of interesting applications: they can simplify the process of rotating encryption keys for encrypted data stored in the cloud, they give one round distributed PRFs, and they can be the basis of a symmetric-key proxy re-encryption scheme. Until now all known constructions

for key homomorphic PRFs were only proven secure in the random oracle model. We construct the first provably secure key homomorphic PRFs in the standard model. Our main construction

is based on the learning with errors (LWE) problem. In the proof of security we need a variant of LWE where query points are non-uniform and we show that this variant is as hard as the standard LWE. We also construct key homomorphic PRFs based on the decision linear assumption in groups with an l-linear map. We leave as an open problem the question of constructing standard model key homomorphic PRFs from more general assumptions.