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

21:17 [Pub][ePrint] High Parallel Complexity Graphs and Memory-Hard Functions, by Joel Alwen and Vladimir Serbinenko

  Motivated by growing importance of parallelism in modern computational systems, we introduce a very natural generalization to a parallel setting of the powerful (sequential) black pebbling game over DAGs. For this new variant, when considering pebbling graphs with with multiple disconnected components (say when modelling the computation of multiple functions in parallel), we demonstrate a significant shortcoming of the two most common types of complexity measures for DAGs inherited from the sequential setting (namely S-complexity and ST-complexity). Thus, to ensure the applicability of the new pebbling game as a tool for proving results about say the \\emph{amortized} hardness of functions being repeatedly evaluated, we introduce a new complexity measure for DAGs called \\emph{cumulative complexity} (CC) and show how it overcomes this problem.\\\\

With the aim of facilitating the new complexity lower-bounds in parallel settings we turn to the task of finding high CC graphs for the parallel pebbling game. First we look at several types of graphs such as certain stacks of superconcentrators, permutation graphs, bit-reversal graphs and pyramid graphs, which are known to have high (even optimally so) complexity in the sequential setting. We show that all of them have much lower parallel CC then one could hope for from a graph of equal size. This motivates our first main technical result, namely the construction of a new family of constant in-degree graphs whose parallel CC approaches maximality to within a polylogarithmic factor.\\\\

The second contribution of this work is to demonstrate an application of these new theoretical tools, in particular to the field of cryptography. Memory-hard function (MHF), introduced by Percival~\\cite{Per09}, have the intuitive goal of leverage the relatively high cost of memory in integrated circuits compared to general purpose computers in order to decrease the attractiveness of using custom circuits to mount brute-force attacks. We provide a new formalization for key property of such functions (overcoming problems with the approach of~\\cite{Per09}) using a new type of \\emph{amortized} computational hardness for families of functions in the (parallel) random oracle model. We motivate the hardness definition by showing how it provides an immediate lower-bound on the monetary cost of repeatedly evaluating such functions in several real-world (parallel) computational environments (e.g. FPGAs, ASICs, Cloud Computers). Indeed, in practice such devices are often the most cost effective means for mounting large-scale brute-force attacks on security relevant functions (such as say Proofs-of-Work and the hash functions used to obscure stored passwords in login servers). As the main technical result of this section, for the family of functions $f_G$ (over strings) characterized via a given DAG $G$, we prove a lower-bound on the hardness of $f_G$ in terms of the parallel CC of $G$. In consequence, we obtain the first provably secure (and intuitively sound) MHF.

14:46 [Job][New] PhD scholarship, University of Auckland, New Zealand

  The Inaugural Sir Vaughan F.R. Jones PhD Scholarship

This prestigious scholarship will fund the research in any area of mathematics of a PhD student supervised by a member of the Department of Mathematics. Selection is based purely on the record and research promise of the candidate. The Jones Scholarship offers an annual stipend of NZ$25,000 (tax free), plus fees, for three years of PhD study.

New Zealand mathematician Vaughan Jones, KNZM FRS FRSNZ FAAAS, was awarded the Fields Medal in 1990. He is Distinguished Professor at both the University of Auckland and Vanderbilt University. He is best known for his work on knot (Jones) polynomials and von Neumann algebras.

Interested candidates are encouraged to contact members of the Department informally concerning possible research projects. For public key cryptography or number theory, please contact Steven Galbraith.

Full applications must be received by August 30, 2014.

15:05 [Event][New] M2MSec'14: First International Workshop on Security and Privacy in M2M Communications

  Submission: 1 June 2014
Notification: 1 July 2014
From October 29 to October 29
Location: San Francisco, USA
More Information:

10:55 [Job][New] Researcher in Boolean Functions, Reliable Communication Group, Department of Informatics, University of Bergen, Norway

  The Reliable Communication Group at the University of Bergen invites applications for a 3-year researcher position in Boolean functions. The position is supposed to start in October 2014.

The candidate is expected to have PhD degree in mathematics or computer science or related disciplines, and have considerable publications in discrete functions.

We are seeking an active researcher with expertise in Boolean functions, discrete mathematics and symmetric cryptography to work within the recently funded project “Discrete functions and their applications in cryptography and mathematics”. The prime objectives of this project are Boolean functions with optimal resistance to various cryptographic attacks (differential, linear, algebraic et al.) and their applications in discrete mathematics (such as commutative semifields, o-polynomials, difference sets, dual hyperovals, regular graphs, m-sequences, codes et al.).

18:17 [Pub][ePrint] Linear Sequential Circuit Approximation of Acterbahn Stream Cipher, by Shazia Afreen

  Achterbahn stream cipher is proposed as a candidate for ECRYPT eSTREAM project which deals with key of length 80-bit. The linear distinguishing attack,which aims at distinguishing the keystream from purely random keystream,is employed to Achterbahn stream cipher. A linear distinguishing attack is based on linear sequential circuit approximation technique which distinguishes statistical bias in the keystream. In order to build the distinguisher, linear approximations of both non-linear feedback shift register (NLFSR) and the non-linear Boolean combining function R:F_2^8→F_2 are used. The keystream sequence generated by this algorithm consist a distinguisher with its probability bias〖 2〗^(-1809). Thus, to distinguish the Achterbahn, we only need 1/ε^2 =〖〖(2〗^1809)〗^2=2^3618 keystream bits and the time complexity is about 10/ε^2 =2^3621.3 which is much higher than the exhaustive key search O(2^80).

15:32 [Job][New] Doctoral Student, Technische Universität Darmstadt, Germany

  The Engineering Cryptographic Protocols Group at TU Darmstadt is looking for a doctoral student in Engineering Cryptographic Protocols for Cloud Computing.

Our group is involved in the two main research centers for IT security in Darmstadt, the Center for Advanced Security Research Darmstadt (CASED) and the European Center for Security and Privacy by Design (EC SPRIDE). We develop new methods and tools to optimize and automatically generate cryptographic protocols. See for details.

The candidate will work in the EU FP 7 research project PRACTICE (Privacy-Preserving Computation in the Cloud),, with the goal of developing, optimizing, and automatically generating secure computation protocols for cloud computing.

The candidate is expected to have a completed Master (or equivalent) degree with excellent grades in IT security, computer science, electrical engineering, mathematics, or a closely related field. Solid knowledge in IT security, applied cryptography, and programming skills is required. Additional knowledge in cryptographic protocols, parallel computing, compiler construction, programming languages, and software engineering is a plus.

Review of applications starts immediately until the position is filled.

Please consult the webpage given below for more details and how to apply.

17:11 [Event][New] LightSEC 2014: Third International Workshop on Lightweight Cryptography

  Submission: 1 June 2014
Notification: 11 July 2014
From September 1 to September 2
Location: Istanbul, Turkey
More Information:

17:10 [Event][New] Workshop on Security and Privacy for Smart Connected Devices 2014

  Submission: 20 May 2014
Notification: 10 July 2014
From September 10 to September 11
Location: Wroclaw, Poland
More Information:

09:17 [Pub][ePrint] Investigating the Feasibility of LEAP+ in ZigBee Specification, by Mohammad Rezaeirad, Muhammad Aamir Iqbal, Dmitri Perkins, Magdy Bayoumi

  The ZigBee specification is an emerging wireless technology designed to address the specific needs of low-cost, low-power wireless sensor networks and is built upon the physical and medium access control layers defined in IEEE 802.15.4 standard for wireless personal area networks (WPANs). A key component for the wide-spread success and applicability of ZigBee-based networking solutions will be its ability to provide enhanced security mechanisms that can scale to hundreds of nodes. Currently, however, an area of concern is the ZigBee key management scheme, which uses a centralized approach that introduces well-known issues of limited scalability and a single point of vulnerability. Moreover, ZigBee key management uses a public key infrastructure. Due to these limitations, we suggest replacing ZigBee key management with a better candidate scheme that is decentralized, symmetric, and scalable while addressing security requirements. In this work, we investigate the feasibility of implementing Localized Encryption and Authentication Protocol (LEAP+), a distributed symmetric based key management. LEAP+ is designed to support multiple types of keys based on the message type that is being exchanged. In this paper, we first conduct a qualitative security analysis of LEAP+ and the current ZigBee key management scheme. Using the QualNet 5.0.2 simulator, we implement LEAP+ on the ZigBee platform for the very first time. Experimental results show that a distributed key management scheme such as LEAP+ provides improved security and offers good scalability.

09:17 [Pub][ePrint] Isogeny graphs with maximal real multiplication, by Sorina Ionica and Emmanuel Thomé

  An isogeny graph is a graph whose vertices are principally polarized

abelian varieties and whose edges are isogenies between these varieties. In

his thesis, Kohel described the structure of isogeny graphs for elliptic

curves and showed that one may compute the endomorphism ring of an elliptic

curve defined over a finite field by using a depth first search algorithm

in the graph. In dimension 2, the structure of isogeny graphs is less understood and existing algorithms for computing endomorphism rings are very expensive.

Our setting considers genus 2 jacobians with complex multiplication,

with the assumptions that the real multiplication subring is maximal and

has class number one. We fully describe the isogeny graphs in that


Over finite fields, we derive a depth first search algorithm for computing endomorphism rings locally at prime numbers, if the real multiplication is maximal. To the best of our knowledge, this is the first DFS-based algorithm in genus 2.

09:17 [Pub][ePrint] Self-Updatable Encryption with Short Public Parameters and Its Extensions, by Kwangsu Lee

  Cloud storage is very popular since it has many advantages, but there is a new threat to cloud storage that was not considered before. {\\it Self-updatable encryption} that updates a past ciphertext to a future ciphertext by using a public key is a new cryptographic primitive introduced by Lee, Choi, Lee, Park, and Yung (Asiacrypt 2013) to defeat this threat such that an adversary who obtained a past-time private key can still decrypt a (previously unread) past-time ciphertext stored in cloud storage. Additionally, an SUE scheme can be combined with an attribute-based encryption (ABE) scheme to construct a powerful revocable-storage ABE (RS-ABE) scheme introduced by Sahai, Seyalioglu, and Waters (Crypto 2012) that provides the key revocation and ciphertext updating functionality for cloud storage.

In this paper, we propose an efficient SUE scheme and its extended schemes. First, we propose an SUE scheme with short public parameters in prime-order bilinear groups and prove its security under a $q$-type assumption. Next, we extend our SUE scheme to a time-interval SUE (TI-SUE) scheme that supports a time interval in ciphertexts. Our TI-SUE scheme has short public parameters and also secure under the $q$-type assumption. Finally, we propose the first large universe RS-ABE scheme with short public parameters in prime-order bilinear groups and prove its security in the selective revocation list model under a $q$-type assumption.