International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service 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).

2013-01-01
16:17 [Pub][ePrint] Time-memory Trade-offs for Near-collisions, by Gaƫtan Leurent

  In this work we consider generic algorithms to find near-collisions

for a hash function. If we consider only hash computations, it is

easy to compute a lower-bound for the complexity of near-collision

algorithms, and to build a matching algorithm. However, this

algorithm needs a lot of memory, and makes than 2^{n/2} memory

accesses. Recently, several algorithms have been proposed without

this memory requirement; they require more hash evaluations, but the

attack is actually more practical. They can be divided in two main

categories: some are based on truncation, and some are based on

covering codes.

In this paper, we give a new insight to the generic complexity of a

near-collision attack. First, we consider time-memory trade-offs for

truncation-based algorithms. For a practical implementation, it seems

reasonable to assume that some memory is available and we show that

taking advantage of this memory can significantly reduce the

complexity. Second, we show a new method combining truncation and

covering codes. The new algorithm is always at least as good as the

previous works, and often gives a significant improvement. We

illustrate our results by giving a 10-near collision for MD5: our

algorithm has a complexity of 2^45.4 using 1TB of memory while the

best previous



16:17 [Pub][ePrint] Non-Interactive Key Exchange, by Eduarda S.V. Freire and Dennis Hofheinz and Eike Kiltz and Kenneth G. Paterson

  Non-interactive key exchange (NIKE) is a fundamental but much-overlooked cryptographic primitive. It appears as a major contribution in the ground-breaking paper of Diffie and Hellman, but NIKE has remained largely unstudied since then. In this paper, we provide different security models for this primitive and explore the relationships between them. We then give constructions for secure NIKE in the Random Oracle Model based on the hardness of factoring and in the standard model based on the hardness of a variant of the decisional Bilinear Diffie Hellman Problem for asymmetric pairings. We also study the relationship between NIKE and public key encryption (PKE), showing that a secure NIKE scheme can be generically converted into an IND-CCA secure PKE scheme. This conversion also illustrates the fundamental nature of NIKE in public key cryptography.



16:17 [Pub][ePrint] Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond, by Shafi Goldwasser and Yael Kalai and Raluca Ada Popa and Vinod Vaikuntanathan and Nickolai Zeldovich

  Functional encryption is a powerful primitive: given an encryption

$\\Enc(x)$ of a value $x$ and a secret key $\\sk_f$ corresponding to a

circuit $f$, it enables efficient computation of $f(x)$ without revealing any additional information about $x$. Constructing functional encryption schemes with succinct ciphertexts that guarantee security for even a single secret key (for a general function $f$) is an important open problem with far reaching applications, which this paper addresses.

Our main result is a functional encryption scheme \\textit{for any general function $f$ of depth $d$, with succinct ciphertexts} whose size grows with the depth $d$ rather than the size of the circuit for $f$. We prove the security of our construction based on the intractability of the learning with error (LWE) problem. More generally, we show how to construct a functional encryption scheme

from \\textit{any} public-index predicate encryption scheme and fully homomorphic encryption scheme.

Previously, the only known constructions of functional encryption were either for specific inner product predicates, or for a weak form of functional encryption where the ciphertext size grows

with the size of the circuit for $f$.

We demonstrate the power of this result, by using it to construct a

\\textit{reusable circuit garbling scheme with input and circuit privacy}: an open problem that was studied extensively by the cryptographic community during the past 30 years since Yao\'s introduction of a one-time circuit garbling method in the mid 80\'s. Our scheme also leads to a new paradigm for general function obfuscation which we call token-based obfuscation. Furthermore, we show applications of our scheme to homomorphic encryption for Turing machines where the evaluation runs in input-specific time rather than worst case time, and to publicly verifiable and secret delegation.





2012-12-28
19:17 [Pub][ePrint] A Coding-Theoretic Approach to Recovering Noisy RSA Keys, by Kenneth G. Paterson and Antigoni Polychroniadou and Dale L. Sibborn

  Inspired by cold boot attacks, Heninger and Shacham (Crypto 2009) initiated the study of the problem of how to recover an RSA private key from a noisy version of that key. They gave an algorithm for the case where some bits of the private key are known with certainty. Their ideas were extended by Henecka, May and Meurer (Crypto 2010) to produce an algorithm that works when all the key bits are subject to error. In this paper, we bring a coding-theoretic viewpoint to bear on the problem of noisy RSA key recovery. This viewpoint allows us to cast the previous work as part of a more general framework. In turn, this enables us to explain why the previous algorithms do not solve the motivating cold boot problem, and to design a new algorithm that does (and more). In addition, we are able to use concepts and tools from coding theory -- channel capacity, list decoding algorithms, and random coding techniques -- to derive bounds on the performance of the previous algorithms and our new algorithm.



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.





2012-12-27
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.