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

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

  Garbled circuits, introduced by Yao in the mid 80s, allow computing a

function f on an input x without leaking anything about f or x besides f(x). Garbled circuits found numerous applications, but every known construction suffers from one limitation: it offers no security if used on multiple inputs x. In this paper, we construct for the first time reusable garbled circuits. The key building block is a new succinct single-key functional encryption scheme.

Functional encryption is an ambitious primitive: given an encryption

Enc(x) of a value x, and a secret key sk_f for a function f, anyone can compute f(x) without learning any other information about x. We

construct, for the first time, a succinct functional encryption

scheme for any polynomial-time function f where succinctness means

that the ciphertext size does not grow with the size of the circuit for f, but only with its depth. The security of our construction is based on the intractability of the Learning with Errors (LWE) problem and holds as long as an adversary has access to a single key sk_f (or even an a priori bounded number of keys for different functions).

Building on our succinct single-key functional encryption scheme, we

show several new applications in addition to reusable garbled circuits, such as a paradigm for general function obfuscation which we call token-based obfuscation, homomorphic encryption for a class of Turing machines where the evaluation runs in input-specific time rather than worst-case time, and a scheme for delegating computation which is publicly verifiable and maintains the privacy of the computation.

05:22 [Pub][ePrint] An Analysis of the EMV Channel Establishment Protocol, by Christina Brzuska and Nigel P. Smart and Bogdan Warinschi and Gaven J. Watson

  With over 1.5~billion debit and credit cards in use worldwide, the EMV system (a.k.a. ``Chip-and-PIN\'\') has become one of the most important deployed cryptographic protocol suites. Recently, the EMV consortium has decided to upgrade the existing RSA based system with a new system relying on Elliptic Curve Cryptography (ECC). One of the central components of the new system is a protocol that enables a card to establish a secure channel with a card reader. In this paper we provide a security analysis of the proposed protocol, we propose minor changes/clarifications to the ``Request for Comments\'\' issued in Nov 2012, and demonstrate that the resulting protocol meets the intended security goals.

The structure of the protocol is one commonly encountered in practice: first run a key-exchange to establish a shared key (which performs authentication and key confirmation), only then use the channel to exchange application messages. Although common in practice, this structure takes the protocol out of the reach of most standard security models for key-exchange. Unfortunately, the only models that can cope with the above structure suffer from some drawbacks that make them unsuitable for our analysis. Our second contribution is to provide new security models for channel establishment protocols. Our models have a more inclusive syntax, are quite general, deal with a realistic notion of authentication (one-sided authentication as required by EMV), and do not suffer from the drawbacks that we identify in prior models.

05:22 [Pub][ePrint] Design Space Exploration and Optimization of Path Oblivious RAM in Secure Processors, by Ling Ren and Xiangyao Yu and Christopher W. Fletcher and Marten van Dijk and Srinivas Devadas

  Keeping user data private is a huge problem both in cloud computing and computation outsourcing. One paradigm to achieve data privacy is to use tamper-resistant processors, inside which users\' private data is decrypted and computed upon. These processors need to interact with untrusted external memory. Even if we encrypt all data that leaves the trusted processor, however, the address sequence that goes off-chip may still leak information. To prevent this address leakage, the security community has proposed ORAM (Oblivious RAM). ORAM has mainly been explored in server/file settings which assume a vastly different computation model than secure processors.

Not surprisingly, naively applying ORAM to a secure processor setting incurs large performance overheads.

In this paper, a recent proposal called Path ORAM is studied. We demonstrate techniques to make Path ORAM practical in a secure processor setting. We introduce background eviction schemes to prevent Path ORAM failure and allow for a performance-driven design space exploration. We propose a concept called super blocks to further improve Path ORAM\'s performance, and also show an efficient integrity verification scheme for Path ORAM. With our optimizations, Path ORAM overhead drops by 41.8%, and SPEC benchmark execution time improves by 52.4% in relation to a baseline configuration. Our work can be used to improve the security level of previous secure processors.

05:22 [Pub][ePrint] A Security Framework for Analysis and Design of Software Attestation, by Frederik Armknecht and Ahmad-Reza Sadeghi and Steffen Schulz and Christian Wachsmann

  Software attestation has become a popular and challenging research topic at many established security conferences with an expected strong impact in practice. It aims at verifying the software integrity of (typically) resource-constrained embedded devices. However, for practical reasons, software attestation cannot rely on stored cryptographic secrets or dedicated trusted hardware. Instead, it exploits side-channel information, such as the time that the underlying device needs for a specific computation. As traditional cryptographic solutions and arguments are not applicable, novel approaches for the design and analysis are necessary. This is certainly one of the main reasons why the security goals, properties and underlying assumptions of existing software attestation schemes have been only vaguely discussed so far, limiting the confidence in their security claims. Thus, putting software attestation on a solid ground and having a founded approach for designing secure software attestation schemes is still an important open problem.

We provide the first steps towards closing this gap. Our first contribution is a security framework that formally captures security goals, attacker models, and various system and design parameters. Moreover, we present a generic software attestation scheme that covers most existing schemes in the literature. Finally, we analyze its security within our framework, yielding sufficient conditions for provably secure software attestation schemes. We expect that such a consolidating work allows for a meaningful security analysis of existing schemes and supports the design of arguably secure software attestation schemes and will inspire new research in this area.

05:22 [Pub][ePrint] Throughput Optimized Implementations of QUAD, by Jason R. Hamlet and Robert W. Brocato

  We present several software and hardware implementations of QUAD, a recently introduced stream cipher designed to be provably secure and practical to implement. The software implementations target both a personal computer and an ARM microprocessor. The hardware implementations target field programmable gate arrays. The purpose of our work was to first find the baseline performance of QUAD implementations, then to optimize our implementations for throughput. Our software implementations perform comparably to prior work. Our hardware implementations are the first known implementations to use random coefficients, in agreement with QUAD\'s security argument, and achieve much higher throughput than prior implementations.

05:22 [Pub][ePrint] Non-malleable Codes from Additive Combinatorics, by Divesh Aggarwal and Yevgeniy Dodis and Shachar Lovett

  Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. Although such codes do not exist if the family of \"tampering functions\" \\cF is completely unrestricted, they are known to exist for many broad tampering families \\cF. One such natural family is the family of tampering functions in the so called {\\em split-state} model. Here the message m is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with L and R {\\em individually}. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model.

Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature, but were either (1) constructed in the random oracle model [DPW10], or (2) relied on advanced cryptographic assumptions (such as non-interactive zero-knowledge proofs and leakage-resilient encryption) [LL12], or (3) could only encode 1-bit messages [DKO13]. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model.

The heart of our construction uses the following new property of the inner-product function over the vector space F_p^n (for any prime p and large enough dimension n): if L and R are uniformly random over F_p^n, and f,g: F_p^n \\rightarrow F_p^n are two arbitrary functions on L and R, the joint distribution (,) is ``close\'\' to the convex combination of \"affine distributions\" {(U,c U+d)| c,d \\in F_p}, where U is uniformly random in F_p. In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so called {\\em Quasi-polynomial Freiman-Ruzsa Theorem} (which was recently established by Sanders [San12] as a step towards resolving the Polynomial Freiman-Ruzsa conjecture [Gre05]).

05:22 [Pub][ePrint] Optical PUFs Reloaded, by Ulrich Rührmair and Christian Hilgers and Sebastian Urban and Agnes Weiershäuser and Elias Dinter and Brigitte Forster and Christian Jirauschek

  We revisit optical physical unclonable functions (PUFs), which were

proposed by Pappu et al. in their seminal first publication on PUFs

[40, 41]. The first part of the paper treats non-integrated optical

PUFs. Their security against modeling attacks is analyzed, and we

discuss new image transformations that maximize the PUF\'s out-

put entropy while possessing similar error correction capacities as

previous approaches [40, 41]. Furthermore, the influence of us-

ing more than one laser beam, varying laser diameters, and smaller

scatterer sizes is systematically studied. Our findings enable the

simple enhancement of an optical PUF\'s security without addi-

tional hardware costs. Next, we discuss the novel application of

non-integrated optical PUFs as so-called \"Certifiable PUFs\". The

latter are useful to achieve practical security in advanced PUF-pro-

tocols, as recently observed by Rührmair and van Dijk at Oakland

2013 [48]. Our technique is the first mechanism for Certifiable

PUFs in the literature, answering an open problem posed in [48].

In the second part of the paper, we turn to integrated optical

PUFs. We build the first prototype of an integrated optical PUF

that functions without moving components and investigate its se-

curity. We show that these PUFs can surprisingly be attacked by

machine learning techniques if the employed scattering structure is

linear, and if the raw interference images of the PUF are available

to the adversary. Our result enforces the use of non-linear scattering

structures within integrated PUFs. The quest for suitable materials is identified as a central, but currently open research problem.

Our work makes intensive use of two prototypes of optical PUFs. The

presented integratable optical PUF prototype is, to our knowledge,

the first of its kind in the literature.

05:22 [Pub][ePrint] AE5 Security Notions: Definitions Implicit in the CAESAR Call, by Chanathip Namprempre and Phillip Rogaway and Tom Shrimpton

  A draft call for the CAESAR authenticated-encryption competition adopts an interface that is not aligned with existing definitions in the literature. It is the purpose of this brief note to formalize what we believe to be the intended definitions.

05:22 [Pub][ePrint] Another Look at Security Theorems for 1-Key Nested MACs, by Neal Koblitz and Alfred Menezes

  We prove a security theorem without collision-resistance for a class of 1-key hash-function-based MAC schemes that includes HMAC and Envelope MAC. The proof has some advantages over earlier proofs: it is in the uniform model, it uses a weaker related-key assumption, and it covers a broad class of MACs in a single theorem. However, we also explain why our theorem is of doubtful value in assessing the real-world security of these MAC schemes. In addition, we prove a theorem assuming collision-resistance. From these two theorems we conclude that from a provable security standpoint there is little reason to prefer HMAC to Envelope MAC or similar schemes.

05:22 [Pub][ePrint] How to Factor N_1 and N_2 When p_1=p_2 mod 2^t, by Kaoru Kurosawa and Takuma Ueda

  Let $N_1=p_1q_1$ and $N_2=p_2q_2$ be two different RSA moduli. Suppose that $p_1=p_2 \\bmod 2^t$ for some $t$, and $q_1$ and $q_2$ are $\\alpha$ bit primes. Then May and Ritzenhofen showed that $N_1$ and $N_2$ can be factored in quadratic time if

\\[ t \\geq 2\\alpha+3. \\]

In this paper, we improve this lower bound on $t$. Namely we prove that $N_1$ and $N_2$ can be factored in quadratic time if

\\[ t \\geq 2\\alpha+1. \\]

Further our simulation result shows that our bound is tight.

05:22 [Pub][ePrint] Fully Homomorphic Encryption for Mathematicians, by Alice Silverberg

  We give an introduction to Fully Homomorphic Encryption for mathematicians. Fully Homomorphic Encryption allows untrusted parties to take encrypted data Enc(m_1),...,Enc(m_t) and any efficiently computable function f, and compute an encryption of f(m_1,...,m_t), without knowing or learning the decryption key or the raw data m_1,...,m_t. The problem of how to do this was recently solved by Craig Gentry, using ideas from algebraic number theory and the geometry of numbers. In this paper we discuss some of the history and background, give examples of Fully Homomorphic Encryption schemes, and discuss the hard mathematical problems on which the cryptographic security is based.