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

04:17 [Pub][ePrint] Selecting Elliptic Curves for Cryptography: An Efficiency and Security Analysis, by Joppe W. Bos and Craig Costello and Patrick Longa and Michael Naehrig

  We select a set of elliptic curves for cryptography and analyze our selection from a performance and security perspective. This analysis complements recent curve proposals that suggest (twisted) Edwards curves by also considering the Weierstrass model. Working with both Montgomery-friendly and pseudo-Mersenne primes allows us to consider more possibilities which improves the overall efficiency of base field arithmetic. Our Weierstrass curves are backwards compatible with current implementations of prime order NIST curves, while providing improved efficiency and stronger security properties. We choose algorithms and explicit formulas to demonstrate that our curves support constant-time, exception-free scalar multiplications, thereby offering high practical security in cryptographic applications. Our implementation shows that variable-base scalar multiplication on the new Weierstrass curves at the 128-bit security level is about 1.4 times faster than the recent implementation record on the corresponding NIST curve. For practitioners who are willing to use a different curve model and sacrifice a few bits of security, we present a collection of twisted Edwards curves with particularly efficient arithmetic that are up to 1.37, 1.27 and 1.25 times faster than the new Weierstrass curves at the 128-, 192- and 256-bit security levels, respectively. Finally, we discuss how these curves behave in a real world protocol by considering different scalar multiplication scenarios in the transport layer security (TLS) protocol.

04:17 [Pub][ePrint] Modelling After-the-fact Leakage for Key Exchange, by Janaka Alawatugoda and Douglas Stebila and Colin Boyd

  Security models for two-party authenticated key exchange (AKE) protocols have developed over time to prove the security of AKE protocols even when the adversary learns certain secret values. In this work, we address more granular leakage: partial leakage of long-term secrets of protocol principals, even after the session key is established. We introduce a generic key exchange security model, which can be instantiated allowing bounded or continuous leakage, even when the adversary learns certain ephemeral secrets or session keys. Our model is the strongest known partial-leakage-based security model for key exchange protocols. We propose a generic construction of a two-pass leakage-resilient key exchange protocol that is secure in the proposed model, by introducing a new concept: the leakage-resilient NAXOS trick. We identify a special property for public-key cryptosystems: pair generation indistinguishability, and show how to obtain the leakage-resilient NAXOS trick from a pair generation indistinguishable leakage-resilient public-key cryptosystem.

04:17 [Pub][ePrint] Efficient Revocable Identity-Based Encryption via Subset Difference Methods, by Kwangsu Lee and Dong Hoon Lee and Jong Hwan Park

  Providing an efficient revocation mechanism for identity-based encryption (IBE) is very important since a user\'s credential (or private key) can be expired or revealed. Revocable IBE (RIBE) is an extension of IBE that provides an efficient revocation mechanism. Previous RIBE schemes essentially use the complete subtree (CS) scheme for key revocation. In this paper, we present a new technique for RIBE that uses the efficient subset difference (SD) scheme or the layered subset difference (LSD) scheme instead of using the CS scheme to improve the size of update keys.

Following our new technique, we first propose an efficient RIBE scheme in prime-order bilinear groups by combining the IBE scheme of Boneh and Boyen and the SD scheme and prove its selective security under the standard assumption. Our RIBE scheme is the first RIBE scheme in bilinear groups that has $O(r)$ number of group elements in update keys. Next, we also propose another RIBE scheme in composite-order bilinear groups and prove its full security under static assumptions. Our RIBE schemes also can be integrated with the LSD scheme to reduce the size of private keys.

04:17 [Pub][ePrint] Efficient Secure and Verifiable Outsourcing of Matrix Multiplications, by Yihua Zhang and Marina Blanton

  With the emergence of cloud computing services, a resource-constrained client can outsource its computationally-heavy tasks to cloud providers. Because such service providers might not be fully trusted by the client, the need to verify integrity of the returned computation result arises. The ability to do so is called verifiable delegation or verifiable outsourcing. Furthermore, the data used in the computation may be sensitive and it is often desired to protect it from the cloud throughout the computation. In this work, we put forward solutions for verifiable outsourcing of matrix multiplications that favorably compare with the state of the art. The cost of verifying the result of computation consists of a single modulo exponentiation and can be further reduced if the cloud is rational (or lazy). A lazy cloud tries to minimize its work by skipping the computation, but does not maliciously corrupt the data. Our solutions achieve several desired features such as data protection, public verifiability, and computation chaining.

04:17 [Pub][ePrint] Kummer strikes back: new DH speed records, by Daniel J. Bernstein and Chitchanok Chuengsatiansup and Tanja Lange and Peter Schwabe

  This paper introduces high-security constant-time variable-base-point Diffie--Hellman software using just 274593 Cortex-A8 cycles, 91460 Sandy Bridge cycles, 90896 Ivy Bridge cycles, or 72220 Haswell cycles. The only higher speed appearing in the literature for any of these platforms is a claim of 60000 Haswell cycles for unpublished software performing arithmetic on a binary elliptic curve.

The new speeds rely on a synergy between (1) state-of-the-art formulas for genus-2 hyperelliptic curves and (2) a modern trend towards vectorization in CPUs. The paper introduces several new techniques for efficient vectorization of Kummer-surface computations.

04:17 [Pub][ePrint] Anonymous Two-Factor Authentication: Certain Goals Are Beyond Attainment, by Ding Wang, Ping Wang, and Debiao He

  Despite a decade of intensive research, it still remains a challenge to design a practical dynamic id-based two-factor authentication scheme, for the designers are confronted with an impressive list of security requirements (e.g., resistance to mart card loss attack) and desirable attributes (e.g., local and secure password update). Dozens of solutions have been proposed, yet most of them are shortly found either unable to satisfy some security requirements or short of important features. To overcome this unsatisfactory situation, researchers often work around it in hopes of a new solution (but no one has succeeded so far), while paying little attention to the question: Whether or not there are inherent limitations (conflicts) that prevents us from designing an ideal scheme that satisfies all of these goals?

In this work, we attempt to provide an answer to this question. We revisit two latest (and reprentative) proposals, i.e. Xie\'s scheme and Li\'s scheme, and explore some inherent conflicts and unavoidable trade-offs in designing such schemes. Our results highly indicate that, under the current widely accepted adversary model, certain goals are beyond attainment. To the best of knowledge, the present study makes the first step towards understanding the underlying evaluation metric for dynamic id-based two-factor authentication, which we believe will facilitate better design of two-factor protocols that offer acceptable trade-offs between usability, security and privacy.

04:17 [Pub][ePrint] Isolated Execution on Many-core Architectures, by Ramya Jayaram Masti and Devendra Rai and Claudio Marforio and Srdjan Capkun

  We explore how many-core platforms can be used to enhance the security of future systems and to support important security properties such as runtime isolation using a small Trusted Computing Base (TCB). We focus on the Intel Single-chip Cloud Computer (SCC) to show that such properties can be implemented in current systems. We design a system called \\archname{} which offers strong security properties while maintaining high performance and flexibility enabled by a small centralized security kernel. We further implement and evaluate the feasibility of our design. Currently, our prototype security kernel is able to execute applications in isolation and accommodate dynamic resource requests from them.

We show that, with minor modifications, many-core architectures can offer some unique security properties, not supported by existing single- and multi-core architectures, such as application context awareness. Context awareness, a new security property that we define and explore in this work, allows each application to discover, without any interaction with the security kernel, which other parts of the system are allowed to interact with it and access its resources. We also discuss how an application can use context awareness to defend itself from an unlikely, yet potentially compromised security kernel.

04:17 [Pub][ePrint] Efficient, Oblivious Data Structures for MPC, by Marcel Keller and Peter Scholl

  We present oblivious implementations of several data structures for secure multiparty computation (MPC) such as arrays, dictionaries, and priority queues. The resulting oblivious data structures have only polylogarithmic overhead compared with their classical counterparts. To achieve this, we give secure multiparty protocols for the ORAM of Shi et al. (Asiacrypt `11) and the Path ORAM scheme of van Dijk et al. (CCS `13), and we compare the resulting implementations. We subsequently use our oblivious priority queue for secure computation of Dijkstra\'s shortest path algorithm on general graphs, where the graph structure is secret. To the best of our knowledge, this is the first implementation of a non-trivial graph algorithm in multiparty computation with polylogarithmic overhead.

We implemented and benchmarked all of our protocols using the SPDZ protocol of Damgaard et al. (Crypto `12), which works in the preprocessing model and ensures active security against an adversary corrupting all but one players. For two parties, the access time for an oblivious array of size 1 million is under 250 ms.

04:17 [Pub][ePrint] Short Signatures from Diffie-Hellman, Revisited: Sublinear Public Key, CMA Security, and Tighter Reduction, by Jae Hong Seo

  Designing practical signature scheme based on the standard assumption such as the Computational Diffie-Hellman (CDH) assumption is important both from a practical and a theoretical point of view. Currently, there are only three standard model CDH-based signature schemes with short signatures due to Waters (EUROCRYPT 2005), Seo, and B\\\"ohl et al. (the merged paper in EUROCRYPT 2013). The Waters signature scheme achieves the Existentail UnForgeability against Chosen Message Attack (EUF-CMA) with nearly optimal reduction. However, this scheme suffers from large public keys. To shorten public key size, Seo and B\\\"ohl et al. proposed new approaches, respectively, but each approach has a weak point rather than the Waters signature scheme; Seo\'s approach could prove only a rather weak security, called the bounded CMA security, and B\\\"ohl et al.\'s approach inherently accompanies a loose reduction.

In this paper, we aim at stepping towards practical EUF-CMA secure signatures with tighter reduction; that is, we achieve sublinear public keys with preserving the same security as the Waters signatures. To this end, we revisit the Seo signature scheme and devise an alternative and simple analysis leading the standard EUF-CMA security with tighter reduction. In particular, our security proof has a reduction loss of $O(\\lambda q)$, which is less than $O(\\sqrt{\\frac{\\lambda}{\\log}}\\lambda q)$ of the original security proof, where $\\lambda$ is the security parameter, and is almost the same as that of the Water signature scheme.

01:17 [Pub][ePrint] Automated Proof for Authorization Protocols of TPM 2.0 in Computational Model (full version), by Weijin Wang, Yu Qin, Dengguo Feng

  We present the first automated proof of the authorization protocols in TPM 2.0 in the computational model. The Trusted Platform Module(TPM) is a chip that enables trust in computing platforms and achieves more security than software alone. The TPM interacts with a caller via a predefined set of commands. Many commands reference TPM-resident structures, and use of them may require authorization. The TPM will provide an acknowledgement once receiving an authorization. This interact ensure the authentication of TPM and the caller. In this paper, we present a computationally sound mechanized proof for authorization protocols in the TPM 2.0. We model the authorization protocols using a probabilistic polynomial-time calculus and prove authentication between the TPM and the caller with the aid of the tool CryptoVerif, which works in the computational model. In addiction, the prover gives the upper bounds to break the authentication between them.

19:17 [Pub][ePrint] Breaking `128-bit Secure\' Supersingular Binary Curves (or how to solve discrete logarithms in $\\F_{2^{4 \\cdot 1223}}$ and $\\F_{2^{12 \\cdot 367}}$), by Robert Granger and Thorsten Kleinjung and Je

  In late 2012 and early 2013 the discrete logarithm problem (DLP) in finite fields of small characteristic underwent a dramatic series of breakthroughs, culminating in a heuristic quasi-polynomial time algorithm, due to Barbulescu, Gaudry, Joux and Thom\\\'e. Using these developments, Adj, Menezes, Oliveira and Rodr\\\'iguez-Henr\\\'iquez analysed the concrete security of the DLP, as it arises from pairings on (the Jacobians of) various genus one and two supersingular curves in the literature. At the $128$-bit security level, they suggested that the new algorithms have no impact on the security of a genus one curve over $\\F_{2^{1223}}$, and reduce the security of a genus two curve over $\\F_{2^{367}}$ to $94.6$ bits. In this paper we propose a new field representation and efficient descent principles, which together demonstrate that the new techniques can be made practical at the 128-bit security level. In particular, we show that the aforementioned genus one curve offers only $59$ bits of security, and we report a total break of the genus two curve. Since these techniques are widely applicable, we conclude that small characteristic pairings should henceforth be considered completely insecure.