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

15:17 [Pub][ePrint] Binary Elligator Squared, by Diego F. Aranha and Pierre-Alain Fouque and Chen Qian and Mehdi Tibouchi and Jean-Christophe Zapalowicz

  Applications of elliptic curve cryptography to anonymity, privacy and

censorship circumvention call for methods to represent uniformly random

points on elliptic curves as uniformly random bit strings, so that, for

example, ECC network traffic can masquerade as random traffic.

At ACM CCS 2013, Bernstein et al. proposed an efficient approach,

called ``Elligator,\'\' to solving this problem for arbitrary elliptic

curve-based cryptographic protocols, based on the use of efficiently

invertible maps to elliptic curves. Unfortunately, such invertible maps

are only known to exist for certain classes of curves, excluding in

particular curves of prime order and curves over binary fields. A variant

of this approach, ``Elligator Squared,\'\' was later proposed by Tibouchi

(FC 2014) supporting not necessarily injective encodings to elliptic

curves (and hence a much larger class of curves), but, although some

rough efficiency estimates were provided, it was not clear how an actual

implementation of that approach would perform in practice.

In this paper, we show that Elligator Squared can indeed be implemented

very efficiently with a suitable choice of curve encodings. More

precisely, we consider the binary curve setting (which was not discussed

in Tibouchi\'s paper), and implement the Elligator Squared bit string

representation algorithm based on a suitably optimized version of the

Shallue--van de Woestijne characteristic 2 encoding, which we show can

be computed using only multiplications, trace and half-trace

computations, and a few inversions.

On the fast binary curve of Oliveira et al. (CHES 2013), our

implementation runs in an average of only 22850 Haswell cycles, making

uniform bit string representations possible for a very reasonable

overhead---much smaller even than Elligator on Edwards curves.

As a side contribution, we also compare implementations of Elligator and

Elligator Squared on a curve supported by Elligator, namely

Curve25519. We find that generating a random point and its uniform

bitstring representation is around 35-40% faster with Elligator for

protocols using a fixed base point (such as static ECDH), but 30-35%

faster with Elligator Squared in the case of a variable base point

(such as ElGamal encryption). Both are significantly slower

than our binary curve implementation.

15:17 [Pub][ePrint] GGHLite: More Efficient Multilinear Maps from Ideal Lattices, by Adeline Langlois and Damien Stehle and Ron Steinfeld

  The GGH Graded Encoding Scheme, based on ideal lattices, is the first plausible approximation to a cryptographic multilinear map. Unfortunately, using the security analysis in the original paper, the scheme requires very large parameters to provide security for its underlying encoding re-randomization process. Our main contributions are to formalize, simplify and improve the efficiency and the security analysis of the re-randomization process in the GGH construction. This results in a new construction that we call GGHLite. In particular, we first lower the size of a standard deviation parameter of the re-randomization process of the original scheme from exponential to polynomial in the security parameter. This first improvement is obtained via a finer security analysis of the

drowning step of re-randomization, in which we apply the

Rényi divergence instead of the conventional statistical distance as a measure of distance between distributions. Our second improvement is to reduce the number of randomizers needed from $\\Omega(n \\log n)$ to $2$, where $n$ is the dimension of the underlying ideal lattices. These two contributions allow us to decrease the bit size of the public parameters from $O(\\lambda^5 \\log \\lambda)$ for the

GGH scheme to $O(\\lambda \\log^2 \\lambda)$ in GGHLite, with respect to the security parameter $\\lambda$ (for a constant multilinearity parameter $\\kappa$).

15:17 [Pub][ePrint] Related-Key Security for Pseudorandom Functions Beyond the Linear Barrier, by Michel Abdalla and Fabrice Benhamouda and Alain Passelègue and Kenneth G. Paterson

  Related-key attacks (RKAs) concern the security of cryptographic primitives in the situation where the key can be manipulated by the adversary. In the RKA setting, the adversary\'s power is expressed through the class of related-key deriving (RKD) functions which the adversary is restricted to using when modifying keys. Bellare and Kohno (Eurocrypt 2003) first formalised RKAs and pin-pointed the foundational problem of constructing RKA-secure pseudorandom functions (RKA-PRFs). To date there are few constructions for RKA-PRFs under standard assumptions, and it is a major open problem to construct RKA-PRFs for larger classes of RKD functions. We make significant progress on this problem. We first show how to repair the Bellare-Cash framework for constructing RKA-PRFs and extend it to handle the more challenging case of classes of RKD functions that contain claws. We apply this extension to show that a variant of the Naor-Reingold function already considered by Bellare and Cash is an RKA-PRF for a class of affine RKD functions under the DDH assumption, albeit with an exponential-time security reduction. We then develop a second extension of the Bellare-Cash framework, and use it to show that the same Naor-Reingold variant is actually an RKA-PRF for a class of degree $d$ polynomial RKD functions under the stronger decisional $d$-Diffie-Hellman inversion assumption. As a significant technical contribution, our proof of this result avoids the exponential-time security reduction that was inherent in the work of Bellare and Cash and in our first result.

15:17 [Pub][ePrint] A Genetic Algorithm for Searching Shortest Lattice Vector of SVP Challenge, by Dan Ding and Guizhen Zhu and Xiaoyun Wang

  In this paper, we propose a genetic algorithm for solving the shortest vector problem (SVP) based on sparse integer representations of short vectors in lattices as chromesomes, which, we prove, can guarantee finding the shortest lattice vector under a Markov chain analysis. Moreover, we also suggest some improvements by introducing heuristic techniques: local search and heuristic pruning. The experimental results show that the genetic algorithm outperforms most enumeration algorithms in running time, and achieves the shortest vectors in larger dimensions under SVP challenge benchmarks

15:17 [Pub][ePrint]


15:17 [Pub][ePrint] Bootstrappable Identity-Based Fully Homomorphic Encryption, by Michael Clear and Ciar\\\'{a}n McGoldrick

  It has been an open problem for a number of years to construct an identity-based fully homomorphic encryption (IBFHE) scheme (first mentioned by Naccache at CHES/CRYPTO 2010). At CRYPTO 2013, Gentry, Sahai and Waters largely settled the problem by presenting leveled IBFHE constructions based on the Learning With Errors problem. However their constructions are not bootstrappable, and as a result, are not ``pure\'\' IBFHE schemes. The major challenge with bootstrapping in the identity-based setting is that it must be possible to non-interactively derive from the public parameters an ``encryption\'\' of the secret key for an arbitrary identity. All presently-known leveled IBFHE schemes only allow bootstrapping if such an ``encryption\'\' of the secret key is supplied out-of-band. In this work, we present a ``pure\'\' IBFHE scheme from indistinguishability obfuscation, and extend the result to the attribute-based setting. Our attribute-based scheme is the first to support homomorphic evaluation on ciphertexts with different attributes. Finally, we characterize presently-known leveled IBFHE schemes with a view to developing a ``compiler\'\' from a leveled IBFHE scheme to a bootstrappable IBFHE scheme, and sufficient conditions are identified.

15:17 [Pub][ePrint]


09:26 [Job][New] Software Security Engineer, CloudFlare Inc.


CloudFlare is looking for a talented software engineer to join our security team. We are working on a number of ambitious projects to secure the web and protect our customers from threats of all sorts. The role of security engineer at CloudFlare is more that of a builder than a breaker. You will have to approach problems with creativity and flexibility and be able to identify and use the best tools for the job or build better ones from scratch. At CloudFlare, we are serious about protecting our customers and advancing the state of the art in computer security.

We are looking for experienced engineers (5+ years of experience preferred) with practical expertise in the areas of:

  • Web Security (web application firewall, authentication, anti-crawler technology, penetration testing)

  • Security Intelligence (IP reputation, machine learning techniques using security data)

  • Systems Security and Trusted Computing (application sandboxing, secure boot, remote attestation, TPMs)

  • Secure Computation and Storage (encrypted databases, data anonymization, secure multi-party computation)

  • Network Security Protocols (DNSSEC, SSL/TLS, SPDY, QUIC, etc.)

  • Applied Cryptography (white-box cryptography, side-channel attacks)


  • Proficiency in C, Go and/or Lua or willingness to learn

  • Experience working on large scale distributed systems and performance-critical applications

  • Desire to create well-crafted software

  • Bonus Points:

  • Contributions to the open source community

  • Understanding of Linux internals

  • Familiarity with compilers or code generation tools

  • Healthy sense of paranoia

  • 2014-06-21
    18:26 [PhD][New] San Ling

      Name: San Ling

    18:26 [PhD][Update] Lei Wei: Analysis of Iterated Block Ciphers

      Name: Lei Wei
    Topic: Analysis of Iterated Block Ciphers
    Category:secret-key cryptography


    A block cipher is the foundation stone of symmetric-key cryptography. Due to its simplicity and high performance, it is often the workhorse for providing confidentiality - one of the primary goals of cryptography. Hence the security of a block cipher is of fundamental importance in the entire infrastructure of cryptography, and therefore block ciphers shall be analyzed and evaluated. This practice is called block cipher cryptanalysis. In this thesis, we analyze a few block ciphers in the classic meet-in-the-middle model and in the recently proposed multidimensional linear cryptanalysis model.

    Besides for encryption, block ciphers are also one of the most versatile building blocks used for constructing many other cryptographic primitives. One such example is the compression function of cryptographic hash functions, and there is a close relation between the security analysis of block ciphers and hash functions. In addition, many dedicated cryptographic hash functions are designed with ideas used in block ciphers. Therefore, it is natural that many block cipher cryptanalysis techniques can be transferred to hash function analysis. In this thesis, we analyze hash functions with differential cryptanalysis and techniques inspired by differential cryptanalysis. On the other hand, recent advances in hash function cryptanalysis contribute to the analysis of block ciphers. We give one such example too.

    In total we have four main topics on (or closely related to) the security analysis of block ciphers.

    1. We study the multidimensional extension to Matsui’s Algorithm 1 and find improvements that lower the attack’s costs. The new attacks are applied to 9-round and 4-round Serpent, with interesting observations on these improvements and the framework.
    2. We study meet-in-the-middle attacks and their application to the hardware-oriented block cipher Ktantan family and reduced DES. Several recent hash function analysis techniques are used f[...]

    18:26 [PhD][New] Elisa Gorla

      Name: Elisa Gorla