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

16:17 [Pub][ePrint] On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography, by Nir Bitansky and Omer Paneth

  The traditional notion of {\\em program obfuscation} requires that an obfuscation $\\tilde{f}$ of a program $f$ computes the exact same function as $f$, but beyond that, the code of $\\tilde{f}$ should not leak any information about $f$. This strong notion of {\\em virtual black-box} security was shown by Barak et al. (CRYPTO 2001) to be impossible to achieve, for certain {\\em unobfuscatable function families}. The same work raised the question of {\\em approximate obfuscation}, where the obfuscated $\\tilde{f}$ is only required to approximate $\\tilde{f}$; that is, $\\tilde{f}$ only agrees with $f$ on some input distribution.

We show that, assuming {\\em trapdoor permutations}, there exist families of {\\em robust unobfuscatable functions} for which even approximate obfuscation is impossible. That is, obfuscation is impossible even if the obfuscated $\\tilde{f}$ only agrees with $f$ with probability slightly more than $\\frac{1}{2}$, on a uniformly sampled input (below $\\frac{1}{2}$-agreement, the function obfuscated by $\\tilde{f}$ is not uniquely defined). Additionally, we show that, assuming only one-way functions, we can rule out approximate obfuscation where $\\tilde{f}$ is not allowed to err, but may refuse to compute $f$ with probability close to $1$.

We then demonstrate the power of robust unobfuscatable functions by exhibiting new implications to resettable protocols that so far have been out of our reach. Concretely, we obtain a new non-black-box simulation technique that reduces the assumptions required for resettably-sound zero-knowledge protocols to {\\em one-way functions}, as well as reduce round-complexity. We also present a new simplified construction of simultaneously resettable zero-knowledge protocols that does not rely on collision-resistent hashing. Finally, we construct a three-message simultaneously resettable $\\WI$ {\\em argument of knowledge} (with a non-black-box knowledge extractor). Our constructions are based on a special kind of ``resettable slots\" that are useful for a non-black-box simulator, but not for a resetting prover.

16:17 [Pub][ePrint] Twisted Edwards-Form Elliptic Curve Cryptography for 8-bit AVR-based Sensor Nodes, by Dalin Chu and Johann Gro{\\ss}sch{\\\"a}dl and Zhe Liu

  Wireless Sensor Networks (WSNs) pose a number of unique security challenges that demand innovation in several areas including the design of cryptographic primitives and protocols. Despite recent progress, the efficient implementation of Elliptic Curve Cryptography (ECC) for WSNs is still a very active research topic and techniques to further reduce the time and energy cost of ECC are eagerly sought. This paper presents an optimized ECC implementation that we developed from scratch to comply with the severe resource constraints of 8-bit sensor nodes such as the MICAz and IRIS motes. Our ECC software uses Optimal Prime Fields (OPFs) as underlying algebraic structure and supports two different families of elliptic curves, namely Weierstra{\\ss}-form and twisted Edwards-form curves. Due to the combination of efficient field arithmetic and fast group operations, we achieve an execution time of $5.9 \\cdot 10^6$ clock

cycles for a full 160-bit scalar multiplication on an 8-bit ATmega128

microcontroller, which is 2.78 times faster than the widely-used TinyECC library. Our implementation also shows that the energy cost of ephemeral ECDH key exchange between two MICAz (or IRIS) motes amounts to only 38.7 mJ per mote (including radio communication). A mote with a standard AA battery pack could theoretically perform up to 174,278 ECDH key exchanges before running out of energy.

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.

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.

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.