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] Key Recovery from State Information of Sprout: Application to Cryptanalysis and Fault Attack, by Subhamoy Maitra and Santanu Sarkar and Anubhab Baksi and Pramit Dey

  Abstract. Design of secure light-weight stream ciphers is an important area in cryptographic hardware & embedded systems and a very recent design by Armknecht and Mikhalev (FSE 2015) has received serious attention that uses shorter internal state and still claims to resist the time-memory-data-tradeoff (TMDTO) attacks. An instantiation of this design paradigm is the stream cipher named Sprout with 80-bit secret key. In this paper we cryptanalyze the cipher and refute various claims. The designers claim that the secret key of Sprout can not be recovered efficiently from the complete state information using a guess and determine attack. However, in this paper, we show that it is possible with a few hundred bits in practical time. More importantly, from around 850 key-stream bits, complete knowledge of NFSR (40 bits) and a partial knowledge of LFSR (around one third, i.e., 14 bits); we can obtain all the secret key bits. This cryptanalyzes Sprout with 2^{54} attempts (considering constant time complexity required by the SAT solver in each attempt, which is around 1 minute in a laptop). This is less than the exhaustive key search. Further, we show how related ideas can be employed to mount a fault attack against Sprout that requires around 120 faults in random locations (20 faults, if the locations are known), whereas the designers claim that such a fault attack may not be possible. Our cryptanalytic results raise quite a few questions about this design paradigm in general that should be revisited with greater care.

12:17 [Pub][ePrint] Fast Revocation of Attribute-Based Credentials for Both Users and Verifiers, by Wouter Lueks and Gergely Alpár and Jaap-Henk Hoepman and Pim Vullers

  Attribute-based credentials allow a user to prove properties about herself anonymously. Revoking such credentials, which requires singling them out, is hard because it is at odds with anonymity. All revocation schemes proposed to date either sacrifice anonymity altogether, require the parties to be online, or put high load on the user or the verifier. As a result, these schemes are either too complicated for low-powered devices like smart cards or they do not scale. We propose a new revocation scheme that has a very low computational cost for users and verifiers, and does not require users to process updates. We trade only a limited, but well-defined, amount of anonymity to make the first practical revocation scheme that is efficient at large scales and fast enough for smart cards.

12:17 [Pub][ePrint] One Time Programs with Limited Memory, by Konrad Durnoga and Stefan Dziembowski and Tomasz Kazana and Michał Zając

  We reinvestigate a notion of {\\em one-time programs} introduced in the CRYPTO 2008 paper by Goldwasser {\\it et~al.} A one-time program is a device containing a program $C$, with the property that the program $C$ can be executed on at most one input. Goldwasser {\\it et~al.}~show how to implement one-time programs on devices equipped with special hardware gadgets called {\\em one-time memory} tokens.

We provide an alternative construction that does not rely on the hardware gadgets. Instead, it is based on the following assumptions: (1) the total amount of data that can leak from the device is bounded, and (2) the total memory on the device (available both to the honest user and to the attacker) is also restricted, which is essentially the model used recently by Dziembowski {\\it et al.}\\ (TCC 2011, CRYPTO 2011) to construct one-time computable {\\em pseudorandom} functions and key-evolution schemes.

04:06 [Job][New] Summer Intern – M.A./M.S./Ph.D. student in Computer Science, Computer Engineering, or Applied Math, IBM Research – Almaden, 650 Harry Road, San Jose, CA 95120-6099, USA

  Design and develop security solutions utilizing vetted cryptographic primitives. Application areas include Internet of Things (IoT), sensors, cyber-physical systems, and cloud and cognitive computing. Architectures must meet security and privacy requirements that involve, in particular, device and/or user identity management under various constraints on connectivity, communications bandwidth, processing complexity, and power consumption.

The investigation may include the use of proxy devices to bridge secure authorized communications between IoT sensor endpoint nodes and data collection-, data processing/analyzing/aggregating-, and feedback/calibration- providing- systems. Robustness against various forms of denial of service should be considered.

3+ years of coding experience in C/C++ is required. Proficiency in programming devices such as Arduino, Raspberry Pi, and BeagleBone Black is a definite plus.

This is a 3-month position with flexible start/end dates during May - September 2015 time frame.

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.