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

00:17 [Pub][ePrint] Boosting OMD for Almost Free Authentication of Associated Data, by Reza Reyhanitabar and Serge Vaudenay and Damian Vizár

  We propose \\emph{pure} OMD (p-OMD) as a new variant of the Offset Merkle-Damg{\\aa}rd (OMD) authenticated encryption scheme. Our new scheme inherits all desirable security features of OMD while having a more compact structure and providing higher efficiency. The original OMD scheme, as submitted to the CAESAR competition, couples a single pass of a variant of the Merkle-Damg{\\aa}rd (MD) iteration with the counter-based XOR MAC algorithm to provide privacy and authenticity. Our improved p-OMD scheme dispenses with the XOR MAC algorithm and is \\emph{purely} based on the MD iteration; hence, the name ``pure\'\' OMD. To process a message of $\\ell$ blocks and associated data of $a$ blocks, OMD needs $\\ell+a+2$ calls to the compression function while p-OMD only requires $\\max\\left\\{\\ell, a\\right\\}+2$ calls. Therefore, for a typical case where $\\ell \\geq a$, p-OMD makes just $\\ell+2$ calls to the compression function; that is, associated data is processed almost freely compared to OMD. We prove the security of p-OMD under the same standard assumption (pseudo-randomness of the compression function) as made in OMD; moreover, the security bound for p-OMD is the same as that of OMD, showing that the modifications made to boost the performance are without any loss of security.

00:17 [Pub][ePrint] The Design Space of Lightweight Cryptography, by Nicky Mouha

  For constrained devices, standard cryptographic algorithms can be too big, too slow or too energy-consuming. The area of lightweight cryptography studies new algorithms to overcome these problems. In this paper, we will focus on symmetric-key encryption, authentication and hashing. Instead of providing a full overview of this area of research, we will highlight three interesting topics. Firstly, we will explore the generic security of lightweight constructions. In particular, we will discuss considerations for key, block and tag sizes, and explore the topic of instantiating a pseudorandom permutation (PRP) with a non-ideal block cipher construction. This is inspired by the increasing prevalence of lightweight designs that are not secure against related-key attacks, such as PRINCE, PRIDE or Chaskey. Secondly, we explore the efficiency of cryptographic primitives. In particular, we investigate the impact on efficiency when the input size of a primitive doubles. Lastly, we provide some considerations for cryptographic design. We observe that applications do not always use cryptographic algorithms as they were intended, which negatively impacts the security and/or efficiency of the resulting implementations.

00:17 [Pub][ePrint] Communication-Optimal Proactive Secret Sharing for Dynamic Groups, by Joshua Baron and Karim El Defrawy and Joshua Lampkins and Rafail Ostrovsky

  Proactive secret sharing (PSS) schemes are designed for settings where long-term confidentiality of secrets has to be guaranteed, specifically, when all participating parties may eventually be corrupted. PSS schemes periodically refresh secrets and reset corrupted parties to an uncorrupted state; in PSS the corruption threshold $t$ is replaced with a corruption rate which cannot be violated. In dynamic proactive secret sharing (DPSS) the number of parties can vary during the course of execution. DPSS is ideal when the set of participating parties changes over the lifetime of the secret or where removal of parties is necessary if they become severely corrupted. This paper presents the first DPSS schemes with optimal amortized, $O(1)$, per-secret communication compared to $O(n^4)$ or $\\exp(n)$ in number of parties, $n$, required by existing schemes. We present perfectly and statistically secure schemes with near-optimal threshold in each case. We also describe how to construct a communication-efficient dynamic proactively-secure multiparty computation (DPMPC) protocol which achieves the same thresholds.

00:17 [Pub][ePrint] Foundations of Reconfigurable PUFs (Full Version), by Jonas Schneider and Dominique Schröder

  A Physically Unclonable Function (PUF) can be seen as a source of randomness that can be challenged with a stimulus and responds in a way that is to some extent unpredictable. PUFs can be used to provide efficient solutions for common cryptographic primitives such as identification/authentication schemes, key storage, and hardware-entangled cryptography.

Moreover, Brzuska et al.~have recently shown, that PUFs can be used to construct UC secure protocols (CRYPTO 2011). Most PUF instantiations, however, only provide a static challenge/response space which limits their usefulness for practical instantiations. To overcome this limitation, Katzenbeisser et al. (CHES 2011) introduced Logically Reconfigurable PUFs (LR-PUFs), with the idea to introduce an ``update\'\' mechanism that changes the challenge/response behaviour without physically replacing or modifying the hardware.

In this work, we revisit LR-PUFs. We propose several new ways to characterize the unpredictability of LR-PUFs covering a broader class of realistic attacks and examine their relationship to each other.

In addition, we reconcile existing constructions with these new characterizations and show that they can withstand stronger adversaries than originally shown.

Since previous constructions are insecure with respect to our strongest unpredictability notion, we propose a secure construction which relies on the same assumptions and is almost as efficient as previous solutions.

00:17 [Pub][ePrint] Analysis of VAES3 (FF2), by Morris Dworkin and Ray Perlner

  The National Institute of Standards and Technology (NIST) specified three methods for format-preserving encryption (FPE) in Draft NIST Special Publication (SP) 800-38G, which was released for public comment in July, 2013. Each method was a mode of operation of the Advanced Encryption Standard (AES). One of the three modes, VAES3, was specified under the name FF2 in the NIST draft. This note describes a theoretical chosen-plaintext attack that shows the security strength of FF2 is less than 128 bits.

00:17 [Pub][ePrint] Black-Box Garbled RAM, by Sanjam Garg and Steve Lu and Rafail Ostrovsky

  Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao\'s garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives.

In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the OT-hybrid model.

00:17 [Pub][ePrint] Authenticated Key Exchange over Bitcoin, by Patrick McCorry and Siamak F. Shahandashti and Dylan Clarke and Feng Hao

  Bitcoin is designed to protect user anonymity (or pseudonymity) in a financial transaction, and has been increasingly adopted by major e-commerce websites such as Dell, Payal and Expedia. While the anonymity of Bitcoin transactions has been extensively studied, little attention has been paid to the security of post-transaction correspondence. In a commercial application, the merchant and the user often need to engage in follow-up correspondence after a Bitcoin transaction is completed, e.g., to acknowledge the receipt of payment, to confirm the billing address, to arrange the product delivery, to discuss refund and so on. Currently, such follow-up correspondence is typically done in plaintext via email with no guarantee on confidentiality. Obviously, leakage of sensitive data from the correspondence (e.g., billing address) can trivially compromise the anonymity of Bitcoin users. In this paper, we initiate the first study on how to realise end-to-end secure communication between Bitcoin users in a post-transaction scenario without requiring any trusted third party or additional authentication credentials. We first point out that none of the existing PKI-based or password-based AKE schemes are suitable for the purpose. Instead, our idea is to leverage the Bitcoin\'s append-only ledger as an additional layer of authentication between previously confirmed transactions. This naturally leads to a new category of AKE protocols that bootstrap trust entirely from the block chain. We call this new category ``Bitcoin-based AKE\'\' and present two concrete protocols: one is non-interactive with no forward secrecy, while the other is interactive with additional guarantee of forward secrecy. Finally, we present proof-of-concept prototypes for both protocols with experimental results to demonstrate their practical feasibility.

00:17 [Pub][ePrint] TinyLEGO: An Interactive Garbling Scheme for Maliciously Secure Two-party Computation, by Tore Kasper Frederiksen and Thomas P. Jakobsen and Jesper Buus Nielsen and Roberto Trifiletti

  This paper reports on a number of conceptual and technical contributions to the currently very lively field of two-party computation (2PC) based on garbled circuits. Our main contributions are as follows:

1. We propose a notion of an interactive garbling scheme, where the garbled circuit is

generated as an interactive protocol between the garbler and the evaluator. The garbled circuit is correct and privacy preserving even if one of the two parties was acting maliciously during garbling. The security notion is game based.

2. We show that an interactive garbling scheme combined with a Universally Composable (UC) secure oblivious transfer protocol can be used in a black-box manner to implement two-party computation (2PC) UC securely against a static and malicious adversary. The protocol abstracts many recent protocols for implementing 2PC from garbled circuits and will allow future designers of interactive garbling schemes to prove security with the simple game based definitions, as opposed to directly proving UC security for each new scheme.

3. We propose a new instantiation of interactive garbling by designing a new protocol in the LEGO family of protocols for efficient garbling against a malicious adversary. The new protocol is based on several new technical contributions and many optimizations, including a highly efficient UC commitment scheme. A theoretical evaluation of the efficiency shows that the instantiation is one to two orders of magnitude faster than the previously most efficient LEGO protocol and that it in general compares favorably to all existing garbling-based 2PC protocols for malicious adversaries.

00:17 [Pub][ePrint] New algorithm for the discrete logarithm problem on elliptic curves, by Igor Semaev

  A new algorithms for computing discrete logarithms on elliptic curves defined over finite fields is suggested. It is based on a new method to find zeroes of summation polynomials. In binary elliptic curves one is to solve a cubic system of Boolean equations. Under a first fall degree assumption

the regularity degree of the system is at most $4$. Extensive experimental data which supports the assumption is provided. An heuristic analysis suggests a new asymptotical complexity bound $2^{c\\sqrt{n\\ln n}}, c\\approx 1.69$ for computing discrete logarithms on an elliptic curve over a field of size $2^n$. For several binary elliptic curves recommended by FIPS the new method performs better than Pollard\'s.

00:17 [Pub][ePrint] Tagged One-Time Signatures: Tight Security and Optimal Tag Size, by Masayuki Abe and Bernardo David and Markulf Kohlweiss and Ryo Nishimaki and Miyako Ohkubo

  We present an efficient structure-preserving tagged one-time signature scheme with tight security reductions to the decision-linear assumption.

Our scheme features short tags consisting of a single group element and

gives rise to the currently most efficient structure-preserving signature scheme based on the decision-liner assumption with constant-size signatures of only 14 group elements, where the record-so-far was 17 elements.

To demonstrate the advantages of our scheme, we revisit the work by Hofheinz and Jager (CRYPTO 2012) and present the currently most efficient tightly secure public-key encryption scheme. We also obtain the first structure-preserving public-key encryption scheme featuring both tight security and public verifiability.

00:17 [Pub][ePrint] Improving Key Recovery to 784 and 799 rounds of Trivium using Optimized Cube Attacks, by Pierre-Alain Fouque and Thomas Vannet

  Dinur and Shamir have described cube attacks at EUROCRYPT \'09 and they have shown how efficient they are on the stream cipher Trivium up to 767 rounds. These attacks have been extended to distinguishers but since this seminal work, no better results on the complexity of key recovery attacks on Trivium have been presented. It appears that the time complexity to compute cubes is expensive and the discovery of linear superpoly also requires the computation of many cubes. In this paper, we increase the number of attacked initialization rounds by improving the time complexity of computing cube and we show attacks that go beyond this bound. We were able to find linear superpoly up to 784 rounds, which leads to an attack requiring $2^{39}$ queries. Using quadratic superpoly, we were also able to provide another attack up to 799 rounds which complexity is $2^{40}$ queries and $2^{62}$ for the exhaustive search part. To achieve such results, we find a way to reduce the density of the polynomials, we look for quadratic relations and we extensively use the Moebius transform to speed up computations for various purposes.