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] Practical Bootstrapping in Quasilinear Time, by Jacob Alperin-Sheriff and Chris Peikert

  Gentry\'s ``bootstrapping\'\' technique (STOC 2009) constructs a fully

homomorphic encryption (FHE) scheme from a ``somewhat homomorphic\'\'

one that is powerful enough to evaluate its own decryption function.

To date, it remains the only known way of obtaining unbounded FHE.

Unfortunately, bootstrapping is computationally very expensive,

despite the great deal of effort that has been spent on improving its

efficiency. The current state of the art, due to Gentry, Halevi, and

Smart (PKC 2012), is able to bootstrap ``packed\'\' ciphertexts (which

encrypt up to a linear number of bits) in time only \\emph{quasilinear}

$\\Otil(\\lambda) = \\lambda \\cdot \\log^{O(1)} \\lambda$ in the security

parameter. While this performance is \\emph{asymptotically} optimal up

to logarithmic factors, the practical import is less clear: the

procedure composes multiple layers of expensive and complex

operations, to the point where it appears very difficult to implement,

and its concrete runtime appears worse than those of prior methods

(all of which have quadratic or larger asymptotic runtimes).

In this work we give \\emph{simple}, \\emph{practical}, and entirely

\\emph{algebraic} algorithms for bootstrapping in quasilinear time, for

both ``packed\'\' and ``non-packed\'\' ciphertexts. Our methods are easy

to implement (especially in the non-packed case), and we believe that

they will be substantially more efficient in practice than all prior

realizations of bootstrapping. One of our main techniques is a

substantial enhancement of the ``ring-switching\'\' procedure of Gentry

et al.~(SCN 2012), which we extend to support switching between two

rings where neither is a subring of the other. Using this procedure,

we give a natural method for homomorphically evaluating a broad class

of structured linear transformations, including one that lets us

evaluate the decryption function efficiently.

15:17 [Pub][ePrint] Injective Encoding to Elliptic Curves, by Pierre-Alain Fouque and Antoine Joux and Mehdi Tibouchi

  For a number of elliptic curve-based cryptographic protocols, it is useful and sometimes necessary to be able to encode a message (a bit string) as a point on an elliptic curve in such a way that the message can be efficiently and uniquely recovered from the point. This is for example the case if one wants to instantiate CPA-secure ElGamal encryption directly in the group of points of an elliptic curve. More practically relevant settings include Lindell\'s UC commitment scheme (EUROCRYPT 2011) or structure-preserving primitives.

It turns out that constructing such an encoding function is not easy in general, especially if one wishes to encode points whose length is large relative to the size of the curve. There is a probabilistic, ``folklore\'\' method for doing so, but it only provably works for messages of length less than half the size of the curve.

In this paper, we investigate several approaches to injective encoding to elliptic curves, and in particular, we propose a new, essentially optimal geometric construction for a large class of curves, including Edwards curves; the resulting algorithm is also quite efficient, requiring only one exponentiation in the base field and simple arithmetic operations (however, the curves for which the map can be constructed have a point of order two, which may be a limiting factor for possible applications). The new approach is based on the existence of a covering curve of genus 2 for which a bijective encoding is known.

15:17 [Pub][ePrint] A Secure and efficient elliptic curve based authentication and key agreement protocol suitable for WSN, by Majid Bayat, Mohammad Reza Aref

  Authentication and key agreement protocols play an important role in wireless sensor communication networks. Recently Xue et al\'. suggested a key agreement protocols for WSN which in this paper we show that the protocol has some security flaws. Also we introduce an enhanced authentication and key agreement protocol for WSN satisfying all the security requirements.

15:17 [Pub][ePrint] NaCl on 8-Bit AVR Microcontrollers, by Michael Hutter and Peter Schwabe

  This paper presents first results of the Networking and Cryptography library (NaCl) on the 8-bit AVR family of microcontrollers. We show that NaCl, which has so far been optimized mainly for different desktop and server platforms, is feasible on resource-constrained devices while being very fast and memory efficient. Our implementation shows that encryption using Salsa20 requires 268 cycles/byte, authentication using Poly1305 needs 195 cycles/byte, a Curve25519 scalar multiplication needs 22,791,579 cycles, signing of data using Ed25519 needs 23,216,241 cycles, and verification can be done within 32,634,713 cycles. All implemented primitives provide at least 128-bit security, run in constant time, do not use secret-data-dependent branch conditions, and are open to the public domain (no usage restrictions).

15:17 [Pub][ePrint] An Accurate Probabilistic Reliability Model for Silicon PUFs, by Roel Maes

  The power of an accurate model for describing a physical process or designing a physical system is beyond doubt. The currently used reliability model for physically unclonable functions (PUFs) assumes an equally likely error for every evaluation of every PUF response bit. This limits an accurate description since experiments show that certain responses are more error-prone than others, but this fixed error rate model only captures average case behavior. We introduce a new PUF reliability model taking this observed heterogeneous nature of PUF cells into account. An extensive experimental validation demonstrates that the new predicted distributions describe the empirically observed data statistics almost perfectly, even considering sensitivity to operational temperature. This allows studying PUF reliability behavior in full detail, including average and worst case probabilities, and is an invaluable tool for designing more efficient and better adapted PUFs and PUF-based systems.

15:17 [Pub][ePrint] An Algebraic Framework for Diffie-Hellman Assumptions, by Alex Escala and Gottfried Herold and Eike Kiltz and Carla R\\`afols and Jorge Villar

  We put forward a new algebraic framework to generalize and

analyze Diffie-Hellman like Decisional Assumptions which allows

us to argue about security and applications by considering only algebraic properties.

Our $D_{\\ell,k}-MDDH$ assumption states that it is hard to decide whether

a vector in $G^\\ell$ is linearly dependent of the columns of some matrix in $G^{\\ell\\times k}$ sampled according to distribution $D_{\\ell,k}$.

It covers known assumptions such as $DDH$, $2-Lin$ (linear assumption), and $k-Lin$ (the $k$-linear assumption).

Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in $m$-linear groups to the irreducibility of certain polynomials which describe the output of $D_{\\ell,k}$.

We use the hardness results to find new distributions for which the $D_{\\ell,k}-MDDH$-Assumption holds generically in $m$-linear groups.

In particular, our new assumptions $2-SCasc$ and $2-ILin$ are generically hard in bilinear groups and, compared to $2-Lin$, have shorter description size, which is a relevant parameter for efficiency in many applications.

These results support using our new assumptions as natural replacements for the $2-Lin$ Assumption which was already used in a large number of applications.

To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any $MDDH$-Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash-proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs.

As an independent contribution we give more efficient NIZK and NIWI proofs for membership in a subgroup of $G^\\ell$, for validity of ciphertexts and for equality of plaintexts. The results imply very significant efficiency improvements for a large number of schemes, most notably Naor-Yung type of constructions.

15:17 [Pub][ePrint] A note on quantum related-key attacks, by Martin Roetteler and Rainer Steinwandt

  In a basic related-key attack against a block cipher, the adversary has access to encryptions under keys that differ from the target key by bit-flips. In this short note we show that for a quantum adversary such attacks are quite powerful: if the secret key is (i) uniquely determined by a small number of plaintext-ciphertext pairs, (ii) the block cipher can be evaluated efficiently, and (iii) a superposition of related keys can be queried, then the key can be extracted efficiently.

15:17 [Pub][ePrint] Delegatable Pseudorandom Functions and Applications, by Aggelos Kiayias and Stavros Papadopoulos and Nikos Triandopoulos and Thomas Zacharias

  We put forth the problem of delegating the evaluation of a

pseudorandom function (PRF) to an untrusted proxy. A {\\em delegatable PRF}, or DPRF for short, is a new primitive that enables a proxy to evaluate a PRF on a strict subset of its domain using a trapdoor derived from the DPRF secret-key. PRF delegation is

\\emph{policy-based}: the trapdoor is constructed with respect to a

certain policy that determines the subset of input values which the

proxy is allowed to compute. Interesting DPRFs should achieve

\\emph{low-bandwidth delegation}: Enabling the proxy to compute the PRF values that conform to the policy should be more efficient than simply providing the proxy with the sequence of all such values precomputed.

The main challenge in constructing DPRFs is in maintaining the

pseudorandomness of unknown values in the face of an attacker that

adaptively controls proxy servers. A DPRF may be optionally equipped

with an additional property we call \\emph{policy privacy}, where any

two delegation predicates remain indistinguishable in the view of a

DPRF-querying proxy: Achieving this raises new design challenges as

policy privacy and efficiency are seemingly conflicting goals.

For the important class of policies described as (1-dimensional)

\\emph{ranges}, we devise two DPRF constructions and rigorously prove

their security. Built upon the well-known tree-based GGM PRF

family~\\cite{GGM86}, our constructions are generic and feature only

logarithmic delegation size in the number of values conforming to the

policy predicate. At only a constant-factor efficiency reduction, we

show that our second construction is also policy private. As we

finally describe, their new security and efficiency properties render

our delegated PRF schemes particularly useful in numerous security

applications, including RFID, symmetric searchable encryption, and

broadcast encryption.

15:17 [Pub][ePrint] Comments on Three Multi-Server Authentication Protocols, by Yalin Chen 1, *Jue-Sam Chou2, Wen-Yi Tsai 3

  Recently, Tsai et al., Liao et al. and Li et al. each proposed a multi-server authentication protocol. They claimed their protocols are secure and can withstand various attacks. However, we found some security loopholes in each of their schemes, for example, both Tsai et al.\'s and Liao et al.\'s schemes suffers from server spoofing attack by an insider server. Li et al.s\' suffers from the lost smart card password-guessing attack. In addition, Liao et al.\'s scheme also has the off-line password-guessing attack. In this paper, we will first review then show the attacks on each of the schemes. Then, based on Li et al.\'s scheme, we proposed a novel one and examined its security in several security features. After security analysis, we concluded that our protocol outperformed Li et al.\'s scheme in the security feature of lost smart card password-guessing attack.

Keywords: multi-server, password authentication protocol

11:22 [Job][New] Senior Scientist Medical Security, Philips Research Europe, Netherlands-North Brabant-Eindhoven

  Your responsibilities:

-Carry out industrial research in medical security and informatics, enlarging relevant knowledge and bringing-in new knowledge;

-Pro-actively make knowledge available for operational use within Philips, such as to contribute to successful transfers of research results to the customer;

-Keep abreast of technical, application and market developments in the relevant technological and industrial areas, showing interest in the business aspects;

-Contribute to the definition of the group\\\'s research program

Contribute pro-actively to a creative and inspiring working environment;

More specifically:

-You perform independent research, define and lead projects in the area of security. The results of your work are adopted by the Philips Healthcare businesses and translated into successful products. You maintain and build close contacts with Philips Healthcare businesses and contribute to the strategy of the research group.

-You create technologies that ensure the security of Philips Healthcare products and services. In addition you contribute security specifications to international standards. You have a full understanding of the state-of-the-art and create original contributions. Important research questions include specification and enforcement of security policies, cloud computing security, authorization and authentication as well as security/risk analysis of specific systems.

-External exposure (for example by means of scientific publications) and external collaborations (for example with universities or in the context of European research projects) are highly encouraged.

Organization description:

Ideal candidate has:

-A PhD in a relevant area (information security and/or cryptography).

-preferably 5 years of preferably applied research experience in the domain of medical security

21:17 [Pub][ePrint] Achieving the limits of the noisy-storage model using entanglement sampling, by Frédéric Dupuis and Omar Fawzi and Stephanie Wehner

  A natural measure for the amount of quantum information that a physical system $E$ holds about another system $A = A_1,...,A_n$ is given by the min-entropy $\\hmin(A|E)$. Specifically, the min-entropy measures the amount of entanglement between $E$ and $A$, and is the relevant measure when analyzing a wide variety of problems ranging from randomness extraction in quantum cryptography, decoupling used in channel coding, to physical processes such as thermalization or the thermodynamic work cost (or gain) of erasing a quantum system. As such, it is a central question to determine the behaviour of the min-entropy after some process M is applied to the system $A$. Here we introduce a new generic tool relating the resulting min-entropy to the original one, and apply it to several settings of interest, including sampling of subsystems and measuring in a randomly chosen basis.

The results on random measurements yield new high-order entropic uncertainty relations with which we prove the optimality of cryptographic schemes in the bounded quantum storage model. This is an abridged version of the paper; the full version containing all proofs and further applications can be found in \\cite{DFW13}.