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

11:56 [Job][New] Ph.D in Information Security, University of Surrey, Guildford (UK)

  The Department of Computing at the University of Surrey ( seeks to recruit a motivated doctoral student to work in the area of Information Security.

The studentship is for three years and includes a stipend of £16,000 per year and tuition fees, and is available to students of UK/EU residency.

The successful candidate will participate in the Formal Methods and Security group (, will work in an exciting international environment and will have the opportunity to participate in the development of the recently launched Surrey Centre for Cyber Security (

The main tasks of the Ph.D. student will be to develop state-of-the-art techniques for the security analysis of real world protocols. In particular, he/she will work in one of the following areas:

- Formal methods applied to security protocols;

- Applied Cryptography and Provable Security.

The position will remain open until a suitable candidate is found so there is no fixed closing date for applications.

10:17 [Pub][ePrint] Cryptanalysis of a (Somewhat) Additively Homomorphic Encryption Scheme Used in PIR, by Tancrède Lepoint and Mehdi Tibouchi

  Private Information Retrieval (PIR) protects users\' privacy in outsourced storage applications and can be achieved using additively homomorphic encryption schemes. Several PIR schemes with a \"real world\" level of practicality, both in terms of computational and communication complexity, have been recently studied and implemented. One of the possible building block is a conceptually simple and computationally efficient protocol proposed by Trostle and Parrish at ISC 2010, that relies on an underlying secret-key (somewhat) additively homomorphic encryption scheme, and has been reused in numerous subsequent works in the PIR community (PETS 2012, FC 2013, NDSS 2014, etc.).

In this paper, we show that this encryption scheme is not one-way: we present an attack that decrypts arbitrary ciphertext without the secret key, and is quite efficient: it amounts to applying the LLL algorithm twice on small matrices. Used against existing practical instantiations of PIR protocols, it allows the server to recover the

users\' access pattern in a matter of seconds.

10:17 [Pub][ePrint] Low Noise LPN: KDM Secure Public Key Encryption and Sample Amplification, by Nico Döttling

  Cryptography based on the Learning Parity with Noise (LPN) problem has several very desirable aspects: Low computational overhead, simple implementation and conjectured post-quantum hardness. Choosing the LPN noise parameter sufficiently low allows for public key cryptography. In this work, we construct the first standard model public key encryption scheme with key dependent message security based solely on the low noise LPN problem. Additionally, we establish a new connection between LPN with a bounded number of samples and LPN with an unbounded number of samples. In essence, we show that if LPN with a small error and a small number of samples is hard, then LPN with a slightly larger error and an unbounded number of samples is also hard. The key technical ingredient to establish both results is a variant of the LPN problem called the extended LPN problem.

10:17 [Pub][ePrint] Group Signatures from Lattices: Simpler, Tighter, Shorter, Ring-based, by San Ling and Khoa Nguyen and Huaxiong Wang

  We introduce a lattice-based group signature scheme that provides several noticeable improvements over the contemporary ones: simpler construction, weaker hardness assumptions, and shorter sizes of keys and signatures. Moreover, our scheme can be transformed into the ring setting, resulting in a scheme based on ideal lattices, in which the public key and signature both have bit-size soft-O(n log N), for security parameter n, and for group of N users. Towards our goal, we construct a new lattice-based cryptographic tool: a statistical zero-knowledge argument of knowledge of a valid message-signature pair for Boyen\'s signature scheme (Boyen, PKC\'10), which potentially can be used as the building block to design various privacy-enhancing cryptographic constructions.

10:17 [Pub][ePrint] One-Round Key Exchange with Strong Security: An Efficient and Generic Construction in the Standard Model, by Florian Bergsma, Tibor Jager, Jörg Schwenk

  One-round authenticated key exchange (ORKE) is an established research area, with many prominent protocol constructions like HMQV (Krawczyk, CRYPTO 2005) and Naxos (La Macchia et al., ProvSec 2007), and many slightly different, strong security models. Most constructions combine ephemeral and static Diffie-Hellman Key Exchange (DHKE), in a manner often closely tied to the underlying security model.

We give a generic construction of ORKE protocols from general assumptions, with security in the standard model, and in a strong security model where the attacker is even allowed to learn the randomness or the long-term secret of either party in the target session. The only restriction is that the attacker must not learn both the randomness and the long-term secret of one party of the target session, since this would allow him to recompute all internal states of this party, including the session key.

This is the first such construction that does not rely on random oracles.

The construction is intuitive, relatively simple, and efficient. It uses only standard primitives, namely non-interactive key exchange, a digital signature scheme, and a pseudorandom function, with standard security properties, as building blocks.

10:17 [Pub][ePrint] Efficient Statically-Secure Large-Universe Multi-Authority Attribute-Based Encryption, by Yannis Rouselakis and Brent Waters

  We propose an efficient large-universe multi-authority ciphertext - policy attribute-based encryption system. In a large-universe ABE scheme, any string can be used as an attribute of the system, and these attributes are not necessarily enumerated during setup. In a multi-authority ABE scheme, there is no central authority that distributes the keys to users. Instead, there are several authorities, each of which is responsible for the authorized key distribution of a specific set of attributes. Prior to our work, several schemes have been presented that satisfy one of these two properties but not both.

Our construction achieves maximum versatility by allowing multiple authorities to control the key distribution for an exponential number of attributes. In addition, the ciphertext policies of our system are sufficiently expressive and overcome the restriction

that ``each attribute is used only once\'\' that constrained previous constructions. Besides versatility, another goal of our work is to increase efficiency and practicality. As a result,

we use the significantly faster prime order bilinear groups rather than composite order groups. The construction is non-adaptively secure in the random oracle model under a non-interactive q-type assumption, similar to one used in prior works. Our work

extends existing ``program-and-cancel\'\' techniques to prove security and introduces two new techniques of independent interest for other ABE constructions. We provide an implementation and some benchmarks of our construction in Charm, a programming framework developed for rapid prototyping of cryptographic primitives.

10:17 [Pub][ePrint] Simple Functional Encryption Schemes for Inner Products, by Michel Abdalla and Florian Bourse and Angelo De Caro and David Pointcheval

  Functional encryption is a new paradigm in public-key encryption that allows users to finely control the amount of information that is revealed by a ciphertext to a given receiver. Recent papers have focused their attention on constructing schemes for general functionalities at expense of efficiency. Our goal, in this paper, is to construct functional encryption schemes for less general functionalities which are still expressive enough for practical scenarios. We propose a functional encryption scheme for the inner-product functionality, meaning that decrypting an encrypted vector x with a key for a vector y will reveal only and nothing else, whose security is based on the DDH assumption.

Despite the simplicity of this functionality, it is still useful in many contexts like descriptive statistics. In addition, we generalize our approach and present a generic scheme that can be instantiated, in addition, under the LWE assumption and offers various trade-offs in terms of expressiveness and efficiency.

10:17 [Pub][ePrint] A linear attack on Kahrobaei-Lam-Shpilrain key exchange protocol, by Jintai Ding, Alexei Miasnikov, Alexander Ushakov

  In this paper we analyze the Kahrobaei-Lam-Shpilrain (KLS) key

exchange protocols that use extensions by endomorpisms of matrices over a Galois field

proposed in 2014.

We show that both protocols are vulnerable to a simple linear algebra attack.

10:17 [Pub][ePrint] Strongly-Optimal Structure Preserving Signatures from Type II Pairings: Synthesis and Lower Bounds, by Gilles Barthe and Edvard Fagerholm and Dario Fiore and Andre Scedrov and Benedikt Schmidt and Meh

  Recent work on structure-preserving signatures studies optimality of these schemes in terms of the number of group elements needed in the verification key and the signature, and the number of pairing-product equations in the verification algorithm. While the size of keys and signatures is crucial for many applications, another important aspect to consider for performance is the time it takes to verify a given signature. By far, the most expensive operation during verification is the computation of pairings. However, the concrete number of pairings that one needs to compute is not captured by the number of pairing-product equations considered in earlier work.

To fill this gap, we consider the question of what is the minimal number of pairings that one needs to compute in the verification of structure-preserving signatures. First, we prove lower bounds for schemes in the Type~II setting that are secure under chosen message attacks in the generic group model, and we show that three pairings are necessary and that at most one of these pairings can be precomputed. We also extend our lower bound proof to schemes secure under random message attacks and show that in this case two pairings are still necessary. Second, we build an automated tool to search for schemes matching our lower bounds. The tool can generate automatically and exhaustively all valid structure-preserving signatures within a user-specified search space, and analyze their (bounded) security in the generic group model. Interestingly, using this tool, we find a new randomizable structure-preserving signature scheme in the Type~II setting that is optimal with respect to the lower bound on the number of pairings, and also minimal with respect to the number of group operations that have to be computed during verification.

10:17 [Pub][ePrint] Simpler Efficient Group Signatures from Lattices, by Phong Q. Nguyen and Jiang Zhang and Zhenfeng Zhang

  A group signature allows a group member to anonymously sign messages on behalf of the group. In the past few years, new group signatures

based on lattice problems have appeared: the most efficient lattice-based constructions are due to Laguillaumie {\\it et al.} (Asiacrypt \'13)

and Langlois {\\it et al.} (PKC \'14). Both have at least $O(n^2\\log^2 n \\log N)$-bit group public key and $O(n\\log^3 n\\log N)$-bit signature,

where $n$ is the security parameter and $N$ is the maximum number of group members. In this paper, we present a simpler lattice-based group signature, which is more efficient by a $O(\\log N)$ factor in both the group public key and the signature size. We achieve this by using a new non-interactive zero-knowledge (NIZK) proof corresponding to a simple identity-encoding function.

The security of our group signature can be reduced to the hardness of SIS and LWE in the random oracle model.

10:17 [Pub][ePrint] Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification, by Xin Li

  Recently, the problem of privacy amplification with an active adversary has received a lot of attention. Given a shared $n$-bit weak random source $X$ with min-entropy $k$ and a security parameter $s$, the main goal is to construct an explicit 2-round privacy amplification protocol that achieves entropy loss $O(s)$. Dodis and Wichs \\cite{DW09} showed that optimal protocols can be achieved by constructing explicit \\emph{non-malleable extractors}. However, the best known explicit non-malleable extractor only achieves $k=0.49n$ \\cite{Li12b} and evidence in \\cite{Li12b} suggests that constructing explicit non-malleable extractors for smaller min-entropy may be hard. In an alternative approach, Li \\cite{Li12} introduced the notion of a non-malleable condenser and showed that explicit non-malleable condensers also give optimal privacy amplification protocols.

In this paper, we give the first construction of non-malleable condensers for arbitrary min-entropy. Using our construction, we obtain a 2-round privacy amplification protocol with optimal entropy loss for security parameter up to $s=\\Omega(\\sqrt{k})$. This is the first protocol that simultaneously achieves optimal round complexity and optimal entropy loss for arbitrary min-entropy $k$. We also generalize this result to obtain a protocol that runs in $O(s/\\sqrt{k})$ rounds with optimal entropy loss, for security parameter up to $s=\\Omega(k)$. This significantly improves the protocol in \\cite{ckor}. Finally, we give a better non-malleable condenser for linear min-entropy, and in this case obtain a 2-round protocol with optimal entropy loss for security parameter up to $s=\\Omega(k)$, which improves the entropy loss and communication complexity of the protocol in \\cite{Li12b}.