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

19:17 [Pub][ePrint] Cryptanalysis of an efficient certificateless two-party authenticated key agreement protocol, by Qingfeng Cheng

  Recently, He et al. (Computers and Mathematics with Applications, 2012, 64(6): 1914-1926) proposed a new efficient certificateless two-party authenticated key agreement protocol. They claimed their protocol was provably secure in the extended Canetti-Krawczyk (eCK) model. In this paper, we will show that their protocol is insecure. A type I adversary, who obtains one party\'s ephemeral private key, can impersonate the party to cheat the other party and compute the shared session key successfully. For overcoming this weakness, we also propose a simple countermeasure.

19:17 [Pub][ePrint] Applications of Polynomial Properties to Verifiable Delegation of Computation and Electronic Voting, by Marc Obrador and Paz Morillo and Sandra Guasch

  This paper presents some proposals of protocols for two types of schemes such as verifiable delegation of computation and remote electronic voting, based on polynomial properties. Our protocols for verifiable delegation of computation are aimed to the efficient evaluation of polynomials, working on schemes where the polynomial and/or the input are kept secret to the server. Our proposal for remote electronic voting allows the verification of vote well-formation upon reception at the voting server, with little overhead of computations for the voter.

19:17 [Pub][ePrint] On the Impossibility of Sender-Deniable Public Key Encryption, by Dana Dachman-Soled

  The primitive of deniable encryption was first introduced by Canetti et al. (CRYPTO, 1997). Deniable encryption is a regular public key encryption scheme with the added feature that after running the protocol honestly and transmitting a message $m$, both Sender and Receiver may produce random coins showing that the transmitted ciphertext was an encryption of any message $m\'$ in the message space. Deniable encryption is a key tool for constructing incoercible protocols, since it allows a party to send one message and later provide apparent evidence to a coercer that a different message was sent. In addition, deniable encryption may be used to obtain \\emph{adaptively}-secure multiparty computation (MPC) protocols and is secure under \\emph{selective-opening} attacks.

Different flavors such as sender-deniable and receiver-deniable encryption, where only the Sender or Receiver can produce fake random coins, have been considered.

Recently, several open questions regarding the feasibility of deniable encryption have been resolved (c.f. (O\'Neill et al., CRYPTO, 2011), (Bendlin et al., ASIACRYPT, 2011)). A fundamental remaining open question is whether it is possible to construct sender-deniable Encryption Schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings.

The primitive of simulatable public key encryption (PKE), introduced by Damg{\\aa}rd and Nielsen (CRYPTO, 2000), is a public key encryption scheme with additional properties that allow oblivious sampling of public keys and ciphertexts. It is one of the low-level primitives used to construct adaptively-secure MPC protocols and was used by O\'Neill et al. in their construction of bi-deniable encryption in the multi-distributional model (CRYPTO, 2011). Moreover, the original construction of sender-deniable encryption with polynomial security given by Canetti et al. can be instantiated with simulatable PKE. Thus, a natural question to ask is whether it is possible to construct sender-deniable encryption with \\emph{super-polynomial security} from simulatable PKE.

In this work, we investigate the possibility of constructing sender-deniable public key encryption from the primitive of simulatable PKE

in a black-box manner. We show that, in fact, there is no black-box construction of sender-deniable encryption with super-polynomial security from simulatable PKE. This indicates that the original construction of sender-deniable public key encryption given by Canetti et al. is in some sense optimal, since improving on it will require the use of non-black-box techniques, stronger underlying assumptions or interaction.

19:17 [Pub][ePrint] On the Security of the Core of PRINCE Against Biclique and Differential Cryptanalysis, by Farzaneh Abed and Eik List and Stefan Lucks

  PRINCE is a modern involutive lightweight cipher which was proposed by Rechberger et al. in 2012. PRINCE uses 64-bit core cipher, which holds the major encryption logic and is wrapped by two key additions. Thus, the security of the cipher is mainly depending on the security properties of the core. In this paper, we present an independent-biclique attack on the full version and also a differential inside-out cryptanalysis on the round-reduced version of the core of PRINCE.

19:17 [Pub][ePrint] Systematic Treatment of Remote Attestation, by Aurelien Francillon and Quan Nguyen and Kasper B. Rasmussen and Gene Tsudik

  Embedded computing devices (such as actuators, controllers and sensors of various sizes) increasingly permeate many aspects of modern life: from medical to automotive, from building and factory automation to weapons, from critical infrastructures to home entertainment. Despite their specialized nature as well as limited resources and connectivity, these devices are now becoming increasingly popular and attractive targets for various attacks, especially, remote malware infestations. There has been a number of research proposals to detect and/or mitigate such attacks. They vary greatly in terms of application generality and underlying assumptions. However, one common theme is the need for Remote Attestation, a distinct security service that allows a trusted party (verifier) to check the internal state of a remote untrusted embedded device (prover).

This paper provides a systematic treatment of Remote Attestation, starting with a precise definition of the desired service and proceeding to its systematic deconstruction into necessary and sufficient properties. These properties are, in turn, mapped into a minimal collection of hardware and software components that results in secure Remote Attestation. One distinguishing feature of this line of research is the need to prove (or, at least argue) architectural minimality; this is rarely encountered in security research. This work also offers some insights into vulnerabilities of certain prior techniques and provides a promising platform for attaining more advanced security services and guarantees.

19:17 [Pub][ePrint] Sampling Discrete Gaussians Efficiently and Obliviously, by Shweta Agrawal and Craig Gentry and Shai Halevi and Amit Sahai

  In this work we construct an algorithm for sampling Discrete Gaussians efficiently and obliviously. Previously discrete Gaussian samplers have been constructed in \\cite{GPV08, Pei10}, where the algorithms take as input a ``high quality\" basis and produce an output whose quality depends on the input basis quality. Our algorithm produces a discrete Gaussian of somewhat worse quality than \\cite{GPV08,Pei10} but with the advantage that it does not require access to an explicit description of the underlying lattice, for example it suffices for our purposes to have encryptions of lattice vectors under an additively homomorphic encryption scheme. At the heart of our work is the fundamental question {\\it how do sums of discrete Gaussians behave?} Unlike their continuous counterparts, discrete Gaussians are not that well understood. We believe that our work fills in some important gaps of this understanding. Our results are already important in enabling the exciting new work on multilinear maps \\cite{GGH12}, and since the questions we resolve arise naturally, we believe that our work will find application in other areas as well.

19:17 [Pub][ePrint] New Impossible Differential Attack on $\\text{SAFER}_{+}$ and $\\text{SAFER}_{++}$, by Jingyuan Zhao and Meiqin Wang and Jiazhe Chen and Yuliang Zheng

  SAFER\\scriptsize + \\normalsize was a candidate block cipher for AES with 128-bit block size and a variable key sizes of 128, 192 or 256 bits. Bluetooth uses customized versions of SAFER\\scriptsize + \\normalsize for security. The numbers of rounds for SAFER\\scriptsize + \\normalsize with key sizes of 128, 192 and 256 are 8, 12 and 16, respectively. SAFER\\scriptsize ++\\normalsize, a variant of SAFER\\scriptsize +\\normalsize, was among the cryptographic primitives selected for the second phase of the NESSIE project. The block size is 128 bits and the key size can take either 128 or 256 bits. The number of rounds for SAFER\\scriptsize ++ \\normalsize is 7 for keys of 128 bits, and 10 for keys of 256 bits. Both ciphers use PHT as their linear transformation.

In this paper, we take advantage of properties of PHT and S-boxes to identify 3.75-round impossible differentials for SAFER\\scriptsize ++ \\normalsize and 2.75-round impossible differentials for SAFER\\scriptsize +\\normalsize, which result in impossible differential attacks on 4-round SAFER\\scriptsize +\\normalsize/128(256), 5-round SAFER\\scriptsize ++\\normalsize/128 and 5.5-round SAFER\\scriptsize ++\\normalsize/256. Our attacks significantly improve previously known impossible differential attacks on 3.75-round SAFER\\scriptsize +\\normalsize/128(256) and SAFER\\scriptsize ++\\normalsize/128(256). Our attacks on SAFER\\scriptsize +\\normalsize/128(256) and SAFER\\scriptsize ++\\normalsize/128(256) represent the best currently known attack in terms of the number of rounds.

19:17 [Pub][ePrint] Attribute-Based Functional Encryption on Lattices, by Xavier Boyen

  We introduce a broad lattice manipulation technique for expressive cryptography, and use it to realize functional encryption for access structures from post-quantum hardness assumptions.

Specifically, we build an efficient key-policy attribute-based encryption scheme, and prove its security in the selective sense from learning-with-errors intractability in the standard model.

19:17 [Pub][ePrint] Practical Yet Universally Composable Two-Server Password-Authenticated Secret Sharing, by Jan Camenisch and Anna Lysyanskaya and Gregory Neven

  Password-authenticated secret sharing (PASS) schemes, first introduced by Bagherzandi et al. at CCS 2011, allow users to distribute data among several servers so that the data can be recovered using a single humanmemorizable password, but no single server (or collusion of servers up to a certain size) can mount an off-line dictionary attack on the password or learn anything about the data. We propose a new, universally composable (UC) security definition for the two-server case (2PASS) in the public-key setting that addresses a number of relevant limitations of the previous, non-UC definition. For example, our definition makes no prior assumptions on the distribution of passwords, preserves security when honest users mistype their passwords, and guarantees secure composition with other protocols in spite of the unavoidable non-negligible success rate of online dictionary attacks. We further present a concrete 2PASS protocol and prove that it meets our definition. Given the strong security guarantees, our protocol is surprisingly efficient: in its most efficient instantiation under the DDH assumption in the random-oracle model, it requires fewer than twenty elliptic-curve exponentiations on the user\'s device. We achieve our results by careful protocol design and by exclusively focusing on the two-server public-key setting.

19:17 [Pub][ePrint] Succinct Non-Interactive Arguments via Linear Interactive Proofs, by Nir Bitansky and Alessandro Chiesa and Yuval Ishai and Rafail Ostrovsky and Omer Paneth

  \\emph{Succinct non-interactive arguments} (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researches have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation.

A common relaxation is a \\emph{preprocessing} SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only $O(1)$ encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have ``escaped the hegemony\'\' of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments.

We present a general methodology for the construction of preprocessing SNARGs, as well as resulting concrete efficiency improvements. Our contribution is three-fold:


We introduce and study a natural extension of the interactive proof model that considers \\emph{algebraically-bounded} provers; this new setting is analogous to the common study of algebraically-bounded ``adversaries\'\' in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) \\emph{linear-interactive proofs} (LIPs) for NP. Our constructions are based on general transformations applied to both \\emph{linear} PCPs (LPCPs) and traditional ``unstructured\" PCPs.


We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of \\emph{linear targeted malleability} (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain \\emph{zero-knowledge} LIPs and SNARGs. Our techniques yield SNARGs \\emph{of knowledge} and thus can benefit from known recursive composition and bootstrapping techniques.


Following this methodology, we exhibit several constructions achieving new efficiency features, such as ``single-ciphertext preprocessing SNARGs\" and improved succinctness-soundness tradeoffs. We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.

19:17 [Pub][ePrint] An ideal multi-secret sharing scheme based on minimal privileged coalitions , by Yun Song , Zhihui Li

  How to construct an ideal multi-secret sharing scheme for general access structures is difficult. In this paper, we solve an open problem proposed by Spiez et al.recently [Finite Fields and

Their Application, 2011(17) 329-342], namely to design an algorithm of privileged coalitions of any length if such coalitions exist. Furthermore, in terms of privileged coalitions, we show that most of the existing multi-secret sharing schemes based on Shamir threshold secret sharing are not perfect by analyzing Yang et al.\'s scheme and Pang et al.\'s scheme. Finally, based on the algorithm mentioned above, we devise an ideal multi-secret sharing scheme for families of access structures, which possesses more vivid authorized sets than

that of the threshold scheme.