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] FORSAKES: A Forward-Secure Authenticated Key Exchange Protocol Based on Symmetric Key-Evolving Schemes, by Mohammad Sadeq Dousti and Rasool Jalili

  This paper suggests a model and a definition for forward-secure authenticated key exchange (AKE) protocols, which can be satisfied without depending on the Diffie-Hellman assumption. Protocols conforming to our model can be highly efficient, since they do not require the resource-intensive modular exponentiations of the Diffie-Hellman protocol. The basic idea is to use key-evolving schemes (KES), where the long-term keys of the system get updated regularly and irreversibly. We also introduce a protocol, called FORSAKES, and prove rigorously that it is a forward-secure AKE protocol in our model. FORSAKES is a very efficient protocol, and can be implemented by merely using hash functions.

04:17 [Pub][ePrint] Optimal Non-Perfect Uniform Secret Sharing Schemes, by Oriol Farràs and Torben Hansen and Tarik Kaced and Carles Padró

  A secret sharing scheme is non-perfect if some subsets of participants cannot recover the secret value but have some information about it. This work is dedicated to the search of efficient non-perfect secret sharing schemes. The efficiency is measured by means of the information ratio, the ratio between the maximum length of the shares and the length of the secret value.

In order to study perfect and non-perfect secret sharing schemes with all generality, we describe the structure of the schemes through their access function, a real function that measures the amount of information that every subset of participants knows about the secret value. We present new tools for the construction of secret sharing schemes. In particular, we construct a secret sharing scheme for every access function.

We extend the connections between polymatroids and perfect secret sharing schemes to the non-perfect ones to find new results on the information ratio. We find a new lower bound on the information ratio that is better than the ones previously known. In particular, this bound is tight for uniform access functions. The access function of a secret sharing scheme is uniform if all participants play the same role in a scheme (e.g. ramp secret sharing schemes). Moreover, we construct a secret sharing scheme with optimal information ratio for every rational uniform access function.

04:17 [Pub][ePrint] Removing Erasures with Explainable Hash Proof Systems, by Michel Abdalla and Fabrice Benhamouda and David Pointcheval

  An important problem in secure multi-party computation is the design of protocols that can tolerate adversaries that are capable of corrupting parties dynamically and learning their internal states. In this paper, we make significant progress in this area in the context of password-authenticated key exchange (PAKE) and oblivious transfer (OT) protocols. More precisely, we first revisit the notion of projective hash proofs and introduce a new feature that allows us to explain any message sent by the simulator in case of corruption, hence the notion of Explainable Projective Hashing. Next, we demonstrate that this new tool generically leads to efficient PAKE and OT protocols that are secure against semi-adaptive adversaries without erasures in the Universal Composability (UC) framework. We then show how to make these protocols secure even against adaptive adversaries, using non-committing encryption, in a much more efficient way than generic conversions from semi-adaptive to adaptive security. Finally, we provide concrete instantiations of explainable projective hash functions that lead to the most efficient PAKE and OT protocols known so far, with UC-security against adaptive adversaries, with or without erasures, in the single global CRS setting.

04:17 [Pub][ePrint] Public-Key Encryption Resilient Against Linear Related-Key Attacks Revisited, by Hui Cui, Yi Mu, Man Ho Au

  Wee (PKC\'12) proposed a generic public-key encryption scheme in the setting of related-key attacks. Bellare, Paterson and Thomson (Asiacrypt\'12) provided a framework enabling related-key attack (RKA) secure cryptographic primitives for a class of non-linear related-key derivation functions. However, in both of their constructions, the instantiations to achieve the full (strong) RKA security are given under the scenario regarding the private key composed of single element. In other words, each element of the private key shares the same modification. However, this is impractical in real world. In this paper, we concentrate on the security of public-key encryption schemes under linear related-key attacks in the setting of multi-element private keys (that is, the private key is composed of more than one element), where an adversary is allowed to tamper any part of this private key stored in a hardware device, and subsequently observe the outcome of a public-key encryption system under this targeted modified private key.We define the security model for RKA secure public-key encryption schemes as chosen-ciphertext and related-key attack (CC-RKA) security, which means that a public-key encryption scheme remains secure even when an adversary is allowed to issue the decryption oracle on linear shifts of any component of the private key. After that, we present a detailed public-key encryption schemes with the private key formed of several elements, of which the CC-RKA security is under the decisional BDH assumption in the standard model.

04:17 [Pub][ePrint] Algebraic Properties of Modular Addition Modulo a Power of Two, by S. M. Dehnavi and Alireza Rahimipour

  Modular addition modulo a power of two, is one of the most applicable operators in symmetric cryptography; therefore, investigating cryptographic properties of this operator has a significant role in design and analysis of symmetric ciphers.

Algebraic properties of modular addition modulo a power of two have been studied for two operands by Braeken in fse\'05. Also, the authors of this paper, have studied this operator, in some special cases, before. In this paper, taking advantage of previous researches in this area, we generalize the algebraic properties of this operator for more than two summands. More precisely, we

determine the algebraic degree of the component Boolean functions of modular addition of arbitrary number of summands modulo a power of two, as a vectorial Boolean function, along with the number of terms and variables in these component functions. As a result, algebraic degrees of the component Boolean functions of Generalized Pseudo-Hadamard Transforms are driven.

04:17 [Pub][ePrint] Efficient Three-Party Computation from Cut-and-Choose, by Seung Geol Choi and Jonathan Katz and Alex J. Malozemoff and Vassilis Zikas

  With relatively few exceptions, the literature on efficient (practical) secure computation has focused on secure two-party computation~(2PC). It is, in general, unclear whether the techniques used to construct practical 2PC protocols---in particular, the \\emph{cut-and-choose} approach---can be adapted to the multi-party setting.

In this work we explore the possibility of using cut-and-choose for practical secure \\emph{three-party} computation. The three-party case has been studied in prior work in the semi-honest setting, and is motivated by the observation that real-world deployments of multi-party computation are likely to involve few parties. We propose a constant-round protocol for three-party computation tolerating any number of malicious parties, whose computational cost is essentially only \\emph{twice} that of state-of-the-art two-party protocols.

04:17 [Pub][ePrint] How to Use Bitcoin to Design Fair Protocols, by Iddo Bentov and Ranjit Kumaresan

  We study a model of fairness in secure computation in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty. We then show how the Bitcoin network can be used to achieve the above notion of fairness in the two-party as well as the multiparty setting (with a dishonest majority). In particular, we propose new ideal functionalities and protocols for fair secure computation and fair lottery in this model.

One of our main contributions is the definition of an ideal primitive, which we call $\\mathcal{F}_{\\mathrm{CR}}^\\star$ ($\\mathrm{CR}$ stands for ``claim-or-refund\'\'), that formalizes and abstracts the exact properties we require from the Bitcoin network to achieve our goals. Naturally, this abstraction allows us to design fair protocols in a hybrid model in which parties have access to the $\\mathcal{F}_{\\mathrm{CR}}^\\star$ functionality, and is otherwise independent of the Bitcoin ecosystem.

We also show an efficient realization of $\\mathcal{F}_{\\mathrm{CR}}^\\star$ that requires only two Bitcoin transactions to be made on the network.

Our constructions also enjoy high efficiency. In a multiparty setting, our protocols only require a constant number of calls to $\\mathcal{F}_{\\mathrm{CR}}^\\star$ per party on top of a standard multiparty secure computation protocol. Our fair multiparty lottery protocol improves over previous solutions which required a quadratic number of Bitcoin transactions.

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.