International Association
for Cryptologic Research

In this paper we describe how to use a secret bug as a trapdoor to design trapped ellliptic curve E(Fp). This trapdoor can be used to mount an invalid curve attack on E(Fp). E(Fp) is designed to respect all ECC security criteria (prime order,high twist order, etc.) but for a secret exponent the point is projected on another unsecure curve. We show how to use this trap with a particular type of time/memory tradeoff to break the ECKCDSA verication process for any public key of the trapped curve. The process is highly undetectable : the chosen defender eort is quadratic in the saboter computational eort. This work provides a concrete hardly detectable and easily deniable example of cryptographic sabotage. While this proof of concept is very narrow, it highlights the necessity of the Full Verifiable Randomness of ECC

We analyze the concrete security of a hash-based signature scheme described in the most recent Internet Draft by McGrew, Fluhrer and Curcio. We perform this analysis in the random-oracle model, where the Merkle-Damg\r{a}rd hash compression function is models as the random oracle. We show that, even with a large number of different keys the attacker can choose from, and a huge computational budget, the attacker succeeds in creating a forgery with negligible probability ($< 2^{-129}$).

ECDSA is a standard digital signature schemes that is widely used in TLS, Bitcoin and elsewhere. Unlike other schemes like RSA, Schnorr signatures and more, it is particularly hard to construct efficient threshold signature protocols for ECDSA (and DSA). As a result, the best-known protocols today for secure distributed ECDSA require running heavy zero-knowledge proofs and computing many large-modulus exponentiations for every signing operation. In this paper, we consider the specific case of two parties (and thus no honest majority) and construct a protocol that is approximately \textit{two orders of magnitude faster} than the previous best. Concretely, our protocol achieves good performance, with a single signing operation for curve P-256 taking approximately 37ms between two standard machine types in Azure (utilizing a single core only). Our protocol is proven secure under standard assumptions using a game-based definition. In addition, we prove security by simulation under a plausible yet non-standard assumption regarding Paillier.

Along with the evolution of Physically Unclonable Functions (PUFs) as a remedy for the shortcomings of conventional key storage and generation methods, numerous successful attacks against PUFs have been proposed in the literature. Among these are machine learning (ML) attacks, ranging from heuristic approaches to provable algorithms, that have attracted great attention. Nevertheless, the issue of dealing with noise has so far not been addressed in this context. Thus, it is not clear to what extent ML attacks can be launched on real-world, noisy PUFs. This paper aims to clarify this issue by focusing on provable ML algorithms, i.e., Probably Approximately Correct (PAC) learning algorithms. We prove that PAC learning algorithms for known PUF families are effective and applicable even in the presence of noise. Our proof relies heavily on the intrinsic properties of these PUF families, namely arbiter, Ring Oscillator (RO), and Bistable Ring (BR) PUF families. In addition to this proof, we introduce a new style of ML algorithms taking advantage of the Fourier analysis principle. We believe that this type of ML algorithms, and the notions related to it can broaden our understanding of PUFs by offering better measures of security.

We present a new approach to secure multiparty computation against a static and malicious dishonest majority. Unlike previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol. Our new approach enables us to do arithmetic computation over arbitrary finite fields such as GF(p) for any prime. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. We do this in two steps, each of independent interest: – First we show how to extend any (possibly interactive two-party) additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality. – We then show how to realize multiplication of commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.

We are witnessing a confluence between applied cryptography and secure hardware systems in enabling secure cloud computing. On one hand, work in applied cryptography has enabled efficient, oblivious data-structure and memory primitives. On the other, secure hardware and the emergence of Intel SGX has enabled a low-overhead and mass market mechanism for isolated execution. These works have disadvantages by themselves. Oblivious memory primitives carry high performance overheads, especially when run non-interactively. Intel SGX, while more efficient, suffers from numerous software-based side-channel attacks. We combine these two lines of work by designing a working prototype library of oblivious memory primitives, which we call ZeroTrace, on top of SGX. To the best of our knowledge, ZeroTrace represents the first oblivious memory primitives running on a real secure hardware platform. ZeroTrace simultaneously enables a dramatic speedup over pure cryptography and protection from software-based side-channel attacks. The core of our design is an efficient and flexible block-level memory controller that provides oblivious execution against any active software adversary, and across asynchronous SGX enclave terminations. Performance-wise, the memory controller can service requests for 4 Byte blocks in 1.2 ms and 1 KB blocks in 6 ms (given a 10 GB dataset). On top of our memory controller, we evaluate Set/Dictionary/List interfaces which can all perform basic operations (e.g., get/put/insert) in 1- 5 ms for a 4-8 Byte block size. Finally, we demonstrate how to re- parameterize our system for the remote oblivious storage setting, where we can service a 4 KB request in 267 ms, at less than an order of magnitude WAN bandwidth overhead.

If $q$ is a prime and $n$ is a positive integer then any two finite fields of order $q^n$ are isomorphic. Elements of these fields can be thought of as polynomials with coefficients chosen modulo $q$, and a notion of length can be associated to these polynomials. A non-trivial isomorphism between the fields, in general, does not preserve this length, and a short element in one field will usually have an image in the other field with coefficients appearing to be randomly and uniformly distributed modulo $q$. This key feature allows us to create a new family of cryptographic constructions based on the difficulty of recovering a secret isomorphism between two finite fields. In this paper we describe a fully homomorphic encryption scheme based on this new hard problem.

Over the last few years, more people perform their social activities on mobile devices, such as mobile payment or mobile wallet. Mobile commerce (m-commerce) refers to manipulating electronic commerce (e-commerce) by using mobile devices and wireless networks. Radio frequency identification(RFID) is a technology which can be employed to complete payment functions on m-commerce. As an RFID subsystem is applied in m-commerce and supply chains, the related security concerns is very important. Recently, Fan et al. have proposed an ultra-lightweight RFID authentication scheme for m-commerce(ULRAS) and claimed that their protocol is enough efficient, and provides a high level of security. In this paper, we show that their protocol is vulnerable to secret disclosure and reader impersonation attacks. Finally, we improve the Fan et al. protocol to present a new one, which is resistant to the mentioned attacks presented in this paper and the other known attacks in the context of RFID authentication. Our proposed improvement does not impose any additional workload on the RFID tag.

The SSL protocol has been widely used for verifying digital identities and to secure Internet traffic since the early days of the web. Although X.509 certificates have been in existence for more than two decades, individual user uptake has been low due to the high cost of issuance and maintenance of such certs. This has led to a situation whereby users are able to verify the identity of an organization or e-commerce retailer via their digital certificate, but organizations have to rely on weak username and password combinations to verify the identity of customers registered with their service. We propose the X509Cloud framework which enables organizations to issue certificates to their users at zero cost, and allows them to securely store and disseminate client certificates using the Bitcoin inspired blockchain protocol. This in turn will enable organizations and individuals to authenticate and to securely communicate with other users on the Internet.

An OT-combiner takes $n$ implementations of the oblivious transfer (OT) functionality, some of which may be faulty, and produces a secure instance of oblivious transfer as long as a large enough number of the candidates are secure. More specifically, an OT-combiner is a 2-party protocol between Alice and Bob which can make several black-box calls to each of the $n$ OT candidates. An adversary can corrupt one of the players and certain number of OT candidates, obtaining their inputs and (in the active case) full control of their outputs and we want the resulting protocol to be secure against such adversary.

In this work we consider perfectly (unconditionally, zero-error) secure OT-combiners and we focus on \emph{minimizing the number of calls} to the candidate OTs.

First, we extend a result from Ishai et. al (ISIT 2014), constructing a perfectly secure single-use (one call per OT candidate) OT-combiner which is secure against active adversaries corrupting one player and at most a tenth of the OT candidates. Ishai et. al obtained the same result for passive adversaries.

Second, we consider a general asymmetric corruption model where an adversary can corrupt different sets of OT candidates depending on whether it is Alice or Bob who is corrupted. We give sufficient and necessary conditions on the existence of an OT combiner with a given number of calls to each server in terms of the existence of secret sharing schemes with certain access structures and share-lengths. This allows us for example to reduce the number of calls needed by known OT combiners, and in fact to determine the optimal number of calls, in some concrete situations even in the symmetric case, e.g. when there are three OT candidates and one of them is corrupted.

We show that the simple and appealing unconditionally sound mix-net due to Abe (Asiacrypt'99) can be augmented to further guarantee anonymity against malicious verifiers. This additional guarantee implies, in particular, that when applying the Fiat-Shamir transform to the mix-net's underlying sub-protocols, anonymity is provably guaranteed for {\em any} hash function.

As our main contribution, we demonstrate how anonymity can be attained, even if most sub-protocols of a mix-net are merely witness indistinguishable (WI). We instantiate our framework with two variants of Abe's mix-net. In the first variant, ElGamal ciphertexts are replaced by an alternative, yet equally efficient, "lossy" encryption scheme. In the second variant, new "dummy" vote ciphertexts are injected prior to the mixing process, and then removed.

Our techniques center on new methods to introduce additional witnesses to the sub-protocols within the proof of security. This, in turn, enables us to leverage the WI guarantees against malicious verifiers. In our first instantiation, these witnesses follow somewhat naturally from the lossiness of the encryption scheme, whereas in our second instantiation they follow from leveraging combinatorial properties of the Benes-network. These approaches may be of independent interest.

Finally, we demonstrate cases in Abe's original mix-net (without modification) where only one witness exists, such that if the WI proof leaks information on the (single) witness in these cases, then the system will not be anonymous against malicious verifiers.

We provide the first constructions of identity-based encryption and hierarchical identity-based encryption based on the hardness of the (Computational) Diffie-Hellman Problem (without use of groups with pairings) or Factoring. Our construction achieves the standard notion of identity-based encryption as considered by Boneh and Franklin [CRYPTO 2001]. We bypass known impossibility results using garbled circuits that make a non-black-box use of the underlying cryptographic primitives.

Motivated by typo correction in password authentication, we investigate cryptographic error-correction of secrets in settings where the distribution of secrets is a priori (approximately) known. We refer to this as the distribution-sensitive setting.

We design a new secure sketch called the layer-hiding hash (LHH) that offers the best security to date. Roughly speaking, we show that LHH saves an additional log H_0(W) bits of entropy compared to the recent layered sketch construction due to Fuller, Reyzin, and Smith (FRS). Here H_0(W) is the size of the support of the distribution W. When supports are large, as with passwords, our new construction offers a substantial security improvement.

We provide two new constructions of typo-tolerant password-based authentication schemes. The first combines a LHH or FRS sketch with a standard slow-to-compute hash function, and the second avoids secure sketches entirely, correcting typos instead by checking all nearby passwords. Unlike the previous such brute-force-checking construction, due to Chatterjee et al., our new construction uses a hash function whose run-time is proportional to the popularity of the password (forcing a longer hashing time on more popular, lower entropy passwords). We refer to this as popularity-proportional hashing (PPH). We then introduce a frame-work for comparing different typo-tolerant authentication approaches. We show that PPH always offers a better time / security trade-off than the LHH and FRS constructions, and for certain distributions outperforms the Chatterjee et al. construction. Elsewhere, this latter construction offers the best trade-off. In aggregate our results suggest that the best known secure sketches are still inferior to simpler brute-force based approaches.

Indistinguishability obfuscation (IO) enables many heretofore out-of-reach applications in cryptography. However, currently all known constructions of IO are based on multilinear maps which are poorly understood. Hence, tremendous research effort has been put towards basing obfuscation on better-understood computational assumptions. Recently, another path to IO has emerged through functional encryption [Anath and Jain, CRYPTO 2015; Bitansky and Vaikuntanathan, FOCS 2015] but such FE schemes currently are still based on multi-linear maps. In this work, we study whether IO could be based on other powerful encryption primitives.

Separations for IO: We show that (assuming that the polynomial hierarchy does not collapse and one-way functions exist) IO cannot be constructed in a black-box manner from powerful all-or-nothing encryption primitives, such as witness encryption (WE), predicate encryption, and fully homomorphic encryption. What unifies these primitives is that they are of the ``all-or-nothing'' form, meaning either someone has the ``right key'' in which case they can decrypt the message fully, or they are not supposed to learn anything.

Stronger Model for Separations: One might argue that fully black-box uses of the considered encryption primitives limit their power too much because these primitives can easily lead to non-black-box constructions if the primitive is used in a self-feeding fashion --- namely, code of the subroutines of the considered primitive could easily be fed as input to the subroutines of the primitive itself. In fact, several important results (e.g., the construction of IO from functional encryption) follow this very recipe. In light of this, we prove our impossibility results with respect to a stronger model than the fully black-box framework of Impagliazzo and Rudich (STOC'89) and Reingold, Trevisan, and Vadhan (TCC'04) where the non-black-box technique of self-feeding is actually allowed.

We construct a pairing based simulation-extractable SNARK (SE-SNARK) that consists of only 3 group elements and has highly efficient verification. By formally linking SE-SNARKs to signatures of knowledge, we then obtain a succinct signature of knowledge consisting of only 3 group elements.

SE-SNARKs enable a prover to give a proof that they know a witness to an instance in a manner which is: (1) succinct - proofs are short and verifier computation is small; (2) zero-knowledge - proofs do not reveal the witness; (3) simulation-extractable - it is only possible to prove instances to which you know a witness, even when you have already seen a number of simulated proofs.

We also prove that any pairing based signature of knowledge or SE-NIZK argument must have at least 3 group elements and 2 verification equations. Since our constructions match these lower bounds, we have the smallest size signature of knowledge and the smallest size SE-SNARK possible.

A number of cryptographic schemes are built from (keyless) permutations, which are either designed in an ad-hoc fashion or are obtained by fixing the key in a block cipher. Security proofs for these schemes, however, idealize this permutation, i.e., making it random and accessible, as an oracle, to all parties. Finding plausible concrete assumptions on such permutations that guarantee security of the resulting schemes has remained an elusive open question.

This paper initiates the study of standard-model assumptions on permutations -- or more precisely, on families of permutations indexed by a {\em public} seed. We introduce the notion of a {\em public-seed pseudorandom permutation} (psPRP), which is inspired by the UCE notion by Bellare, Hoang, and Keelveedhi (CRYPTO '13). It considers a two-stage security game, where only the second stage learns the seed, and the first-stage adversary, known as the source, is restricted to prevent trivial attacks -- the security notion is consequently parameterized by the class of allowable sources. To this end, we define in particular unpredictable and reset-secure sources analogous to similar notions for UCEs.

We first study the relationship between psPRPs and UCEs. To start with, we provide efficient constructions of UCEs from psPRPs for both reset-secure and unpredictable sources, thus showing that most applications of the UCE framework admit instantiations from psPRPs. We also show a converse of this statement, namely that the five-round Feistel construction yields a psPRP for reset-secure sources when the round function is built from UCEs for reset-secure sources, hence making psPRP and UCE equivalent notions for such sources.

In addition to studying such reductions, we suggest generic instantiations of psPRPs from both block ciphers and (keyless) permutations, and analyze them in ideal models. Also, as an application of our notions, we show that a simple modification of a recent highly-efficient garbling scheme by Bellare et al. (S&P '13) is secure under our psPRP assumption.

We give a new class of security definitions for authentication in the quantum setting. These definitions capture and strengthen existing definitions of security against quantum adversaries for both classical message authentication codes (MACs) as well as full quantum state authentication schemes. The main feature of our definitions is that they precisely characterize the effective behavior of any adversary when the authentication protocol accepts, including correlations with the key. Our definitions readily yield a host of desirable properties and interesting consequences; for example, our security definition for full quantum state authentication implies that the entire secret key can be re-used if the authentication protocol succeeds. Next, we present several protocols satisfying our security definitions. We show that the classical Wegman-Carter authentication scheme with 3-universal hashing is secure against superposition attacks, as well as adversaries with quantum side information. We then present conceptually simple constructions of full quantum state authentication. Finally, we prove a lifting theorem which shows that, as long as a protocol can securely authenticate the maximally entangled state, it can securely authenticate any state, even those that are entangled with the adversary. Thus, this shows that protocols satisfying a fairly weak form of authentication security automatically satisfy a stronger notion of security (in particular, the definition of Dupuis, et al (2012)).

Proving tight bounds on information-theoretic indistinguishability is a central problem in symmetric cryptography. This paper introduces a new method for information-theoretic indistinguishability proofs, called ``the chi-squared method''. At its core, the method requires upper-bounds on the so-called $\chi^2$ divergence (due to Neyman and Pearson) between the output distributions of two systems being queries. The method morally resembles, yet also considerably simplifies, a previous approach proposed by Bellare and Impagliazzo (ePrint, 1999), while at the same time increasing its expressiveness and delivering tighter bounds.

We showcase the chi-squared method on some examples. In particular: (1) We prove an optimal bound of $q/2^n$ for the XOR of two permutations, and our proof considerably simplifies previous approaches using the $H$-coefficient method, (2) we provide improved bounds for the recently proposed encrypted Davies-Meyer PRF construction by Cogliati and Seurin (CRYPTO '16), and (3) we give a tighter bound for the Swap-or-not cipher by Hoang, Morris, and Rogaway (CRYPTO '12).

HACL* is a new verified cryptographic library that implements popular modern cryptographic primitives such as the ChaCha20 and Salsa20 encryption algorithms, Poly1305 and HMAC authentication, SHA-256 and SHA-512 hash functions, the Curve25519 elliptic curve Diffie-Hellman group, and Ed25519 signatures. Using these primitives, HACL* implements the NaCl cryptographic API and can be used as a drop-in replacement for NaCl implementations like libsodium and TweetNaCl. HACL* also provides the cryptographic components for one of the mandatory ciphersuites of TLS 1.3, and is already being used within the miTLS verified implementation.

HACL* is written and verified in the F* programming language and then compiled to readable C code. The F* source code is verified for side-channel mitigations, memory safety, and functional correctness with respect to succinct high-level specifications derived from the standard specification for each cryptographic primitive. The translation to C preserves these properties and the generated code can itself be compiled via the CompCert verified C compiler or mainstream compilers like GCC or CLANG.

When compiled with GCC on 64-bit platforms, our implementations are as fast as the fastest C implementations in OpenSSL and libsodium, significantly faster than the reference C code in TweetNaCl and SuperCop, and between 3x-5x of hand-optimized assembly code. We show how to verify code that relies on low-level hardware features like 128-bit integers and vector instructions. A distinctive feature of HACL* is that we aggressively try to share code and verification effort across primitives, while preserving performance. Our results show that writing fast, verified, and self-contained C cryptographic libraries is now practical.

Event date: 15 November to 17 November 2017
Submission deadline: 3 September 2017