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

22:35 [Job][New] PhD studentship, University College London, United Kingdom, European Union

  We are looking for outstanding candidates for a fully funded PhD studentship in cryptography. The PhD studentship is funded by an ERC Starting Grant on Efficient Cryptographic Arguments and Proofs. The studentship will provide a tax-free annual stipend of £21,000, however, ERC funding does not cover student fees (currently £4,400 for UK/EU students and £20,250 for Overseas students).

The goal of the PhD studentship under the supervision of Dr Jens Groth is to develop new and efficient zero-knowledge techniques. Zero-knowledge proofs enable a prover to convince a verifier that a statement is true without revealing any other information and are widely used in cryptographic protocols.

University College London has been recognized by the EPSRC and GCHQ as an Academic Centre of Excellence in Cyber Security Research and is one of the highest ranked universities in Europe. The Computer Science Department is one of the largest in the UK and is located at UCL\\\'s main campus in the centre of London.

18:17 [Pub][ePrint] Automated Security Proofs for Almost-Universal Hash for MAC verification, by Martin Gagné and Pascal Lafourcade and Yassine Lakhnech

  Message authentication codes (MACs) are an essential primitive in cryptography. They are used to ensure the integrity and authenticity of a message, and can also be used as a building block for larger schemes, such as chosen-ciphertext secure encryption, or identity-based encryption. MACs are often built in two steps: first, the `front end\' of the MAC produces a short digest of the long message, then the `back end\' provides a mixing step to make the output of the MAC unpredictable for an attacker. Our verification method follows this structure. We develop a Hoare logic for proving that the front end of the MAC is an almost-universal hash function. The programming language used to specify these functions is fairly expressive and can be used to describe many block-cipher and compression function-based MACs. We implemented this method into a prototype that can automatically prove the security of almost-universal hash functions. This prototype can prove the security of the front-end of many CBC-based MACs (DMAC, ECBC, FCBC and XCBC to name only a few), PMAC and HMAC. We then provide a list of options for the back end of the MAC, each consisting of only two or three instructions, each of which can be composed with an almost-universal hash function to obtain a secure MAC.

18:17 [Pub][ePrint] Highly Controlled, Fine-grained Delegation of Signing Capabilities, by Michael Backes and Sebastian Meiser and Dominique Schröder

  Delegation of signing rights is a central problem in security. Whereas delegating by giving power of attorney is well studied and digitally realized via delegatable anonymous credentials, directly delegating signing possibilities without the need for an external logic, can be done via malleable signature schemes. However, the existing schemes do not allow for privacy preserving, fine-grained malleability and they do not allow for a controlled way of further delegating the malleability. We bridge this gap by introducing delegatable functional signatures (DFS).

18:17 [Pub][ePrint] Order-Preserving Encryption Secure Beyond One-Wayness, by Tal Malkin and Isamu Teranishi and Moti Yung

  Semantic-security of individual bits under a ciphertext are fundamental notion in modern cryptography. In this work we present the first results about this fundamental problem for Order-Preserving Encryption (OPE): ``what plaintext information can be semantically hidden by OPE encryptions?\'\' While OPE has gained much attention in recent years due to its usefulness in secure databases, any partial-plaintext indistinguishability (semantic security) result for it was open. Here, we propose a new indistinguishability-based security notion for OPE, which can ensure \\emph{secrecy of lower bits of a plaintext} (under essentially a random ciphertext probing setting). We then propose a new scheme satisfying this security notion (while earlier schemes do not satisfy it!). We note that the known security notions tell us nothing about the above partial- plaintext indistinguishability because they are limited to being one-way-based. In addition, we show that our security notion with specific parameters implies the known security notion called WOW, and further, our scheme achieves WOW with better parameters than earlier schemes.

18:17 [Pub][ePrint] Plug-and-Play IP Security: Anonymity Infrastructure Instead of PKI, by Yossi Gilad and Amir Herzberg

  We present the Plug-and-Play IP Security (PnP-IPsec) protocol. PnP-IPsec automatically establishes IPsec security associations between gateways, avoiding the need for manual administration and coordination between gateways, and the dependency on IPsec public key certificates - the two problems which are widely believed to have limited the use of IPsec mostly to intra-organization communication.

PnP-IPsec builds on Self-validated Public Data Distribution (SvPDD), a protocol that we present to establish secure connections between remote peers/networks, without depending on pre-distributed keys or certification infrastructure. Instead, SvPDD uses available anonymous communication infrastructures such as Tor, which we show to allow detection of MitM attacker interfering with communication. SvPDD may also be used in other scenarios lacking secure public key distribution, such as the initial connection to an SSH server.

We provide an open-source implementation of PnP-IPsec and SvPDD, and show that the resulting system is practical and secure.

18:17 [Pub][ePrint] Security Analysis of Lightweight Authentication Protocol from WISTP 2013, by Wang Shao-Hui, Xiao Fu, Chen Dan-wei, Wang Ru-chuan

  One of the key problems in Radio Frequency Identification (RFID) is security and privacy. Many RFID authentication protocols have been proposed to preserve security and privacy of the system. Nevertheless, most of these protocols are analyzed and it is shown that they can not provide security against some RFID attacks. In WISTP 2013, a new lightweight authentication protocol using AES S-box and some special function is presented. The new protocol has a good implementation in resource constrained tags. In this paper, we give the security analysis on this new authentication protocol. After impersonating the valid reader to query the tag and collecting the responses, we can deduce all the secrets shared between the reader and tag through analyzing the messages. The attack utilizes the structure of the invertible function and the property of the special function introduced in the new protocol.

18:17 [Pub][ePrint] Moduar Form Aprroach to Solving Lattice Problems, by Yuan Tian, Xueyong Zhu, Rongxin Sun

  We construct new randomized algorithms to find the exact solution to the shortest and closest vector problems (SVP and CVP) in Euclidean norm (l2) for the integral lattice. Not only the minimal norm of non-zero lattice vectors in SVP and the minimal distance in CVP, but also how many lattice vectors reach those minimums can be simultaneously computed by the algorithms. Our approach is based on some special properties of the generating function of lattice vectors\' (l2-)norms, the lattice-associated theta function, which is used in prior works mainly for hardness analysis on lattice problems but rarely for computational purposes. Such function\'s modular properties are exploited to develop our SVP and CVP solvers. In computational complexity perspective and take our SVP solver as an example, for the integral lattice family {Λn} of dimension dimΛn=n and level h=l(Λn) (the minimal positive integer such that the dual lattice Λn* scaled by h1/2 is integral) polynomial in n, the case frequently occurring in applications, this algorithm can find the minimal l2-norm of non-zero lattice vectors and the number of such shortest vectors in Λn with success probability 1-ε in asymptotic space complexity of polynomial in n and asymptotic time complexity of nO(n)log(1/ε). The only contribution to the algorithm\'s exponential time complexity nO(n)log(1/ε) comes from independently repeating a randomized lattice vector sampler nO(n)log(1/ε) times. All the rest of operations contribute to the algorithm\'s time-complexity only with an additive polynomial in n. Similar situations occur when solving the exact CVP by our algorithm. In other words, our solvers can be easily parallelized to be polynomial in time complexity. In addition, a variant of our CVP solver can solve the closest vector problem with preprocessing (CVPP) in polynomial time and nO(n)log(1/ε) space complexity.

18:17 [Pub][ePrint] Policy-Based Signatures, by Mihir Bellare and Georg Fuchsbauer

  We introduce signatures where signers can only sign messages that conform to some policy, yet privacy of the policy is maintained. We provide definitions and show that policy-based signatures provide a framework which yields a unified view of many other existing types of signatures that now appear as special cases. We also show how still other primitives are easily realized using policy-based signatures as a building block. We provide generic constructions of policy-based signatures and then show how to achieve them efficiently.

18:17 [Pub][ePrint] A novel certificateless deniable authentication protocol, by Chunhua Jin, Chunxiang Xu, Xiaojun Zhang, Qianna Xie, Fagen Li

  Deniable authenticated protocol is a new and attractive protocol compared to the traditional authentication protocol. It allows the appointed receiver to identify the source of a given message, but not to prove the identity of the sender to a third party even if the appointed receiver is willing to reveal its private key. In this paper, we first define a security model for certificateless deniable authentication protocols. Then we propose a non-interactive certificateless deniable authentication protocol, by combining deniable authentication protocol with certificateless cryptography. In addition, we prove its security in the random oracle model.

18:17 [Pub][ePrint] Short collision search in arbitrary SL2 homomorphic hash functions, by Ciaran Mullan and Boaz Tsaban

  We study homomorphic hash functions into SL2(q), the 2x2 matrices with determinant 1 over the

field with q elements.

Modulo a well supported number theoretic hypothesis, which holds in particular for all concrete

homomorphisms proposed thus far, we prove that

a random homomorphism is at least as secure as any concrete homomorphism.

For a family of homomorphisms containing several concrete proposals in the literature,

we prove that collisions of length O(log q) can be found in running time O(sqrt q).

For general homomorphisms we offer an algorithm that, heuristically and according to experiments,

in running time O(sqrt q) finds collisions of length O(log q) for q even, and length O(log^2 q/loglog q) for arbitrary q.

For any conceivable practical scenario, our algorithms are substantially faster than all earlier algorithms

and produce much shorter collisions.

18:17 [Pub][ePrint] Computational Fuzzy Extractors, by Benjamin Fuller and Xianrui Meng and Leonid Reyzin

  Fuzzy extractors derive strong keys from noisy sources. Their security is defined information- theoretically, which limits the length of the derived key, sometimes making it too short to be useful. We ask whether it is possible to obtain longer keys by considering computational security, and show the following.

-Negative Result: Noise tolerance in fuzzy extractors is usually achieved using an information reconciliation component called a \"secure sketch.\" The security of this component, which directly affects the length of the resulting key, is subject to lower bounds from coding theory. We show that, even when defined computationally, secure sketches are still subject to lower bounds from coding theory. Specifically, we consider two computational relaxations of the information-theoretic security requirement of secure sketches, using conditional HILL entropy and unpredictability entropy. For both cases we show that computational secure sketches cannot outperform the best information-theoretic secure sketches in the case of high-entropy Hamming metric sources.

-Positive Result: We show that the negative result can be overcome by analyzing computational fuzzy extractors directly. Namely, we show how to build a computational fuzzy extractor whose output key length equals the entropy of the source (this is impossible in the information-theoretic setting). Our construction is based on the hardness of the Learning with Errors (LWE) problem, and is secure when the noisy source is uniform or symbol-fixing (that is, each dimension is either uniform or fixed). As part of the security proof, we show a result of independent interest, namely that the decision version of LWE is secure even when a small number of dimensions has no error.