Skip to main content

Über dieses Buch

The two-volume proceedings LNCS 9056 + 9057 constitutes the proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, held in Sofia, Bulgaria, in April 2015. The 57 full papers included in these volumes were carefully reviewed and selected from 194 submissions. The papers are organized in topical sections named: honorable mentions, random number generators, number field sieve, algorithmic cryptanalysis, symmetric cryptanalysis, hash functions, evaluation implementation, masking, fully homomorphic encryption, related-key attacks, fully monomorphic encryption, efficient two-party protocols, symmetric cryptanalysis, lattices, signatures, zero-knowledge proofs, leakage-resilient cryptography, garbled circuits, crypto currencies, secret sharing, outsourcing computations, obfuscation and e-voting, multi-party computations, encryption, resistant protocols, key exchange, quantum cryptography, and discrete logarithms.





Universal Signature Aggregators

We introduce the concept of universal signature aggregators. In a universal signature aggregator system, a third party, using a set of common reference parameters, can aggregate a collection of signatures produced from any set of signing algorithms (subject to a chosen length constraint) into one short signature whose length is independent of the number of signatures aggregated. In prior aggregation works, signatures can only be aggregated if all signers use the same signing algorithm (e.g., BLS) and shared parameters. A universal aggregator can aggregate across schemes even in various algebraic settings (e.g., BLS, RSA, ECDSA), thus creating novel opportunities for compressing authentication overhead. It is especially compelling that existing public key infrastructures can be used and that the signers do not have to alter their behavior to enable aggregation of their signatures.
We provide multiple constructions and proofs of universal signature aggregators based on indistinguishability obfuscation and other supporting primitives. We detail our techniques as well as the tradeoffs in features and security of our solutions.
Susan Hohenberger, Venkata Koppula, Brent Waters

Fully Structure-Preserving Signatures and Shrinking Commitments

Structure-preserving signatures are schemes in which public keys, messages, and signatures are all collections of source group elements of some bilinear groups. In this paper, we introduce fully structure-preserving signature schemes, with the additional requirement that even secret keys should be group elements. This new type of structure-preserving signatures allows for efficient non-interactive proofs of knowledge of the secret key and is useful in designing cryptographic protocols with strong security guarantees based on the simulation paradigm where the simulator has to extract the secret keys on-line. To gain efficiency, we construct shrinking structure-preserving trapdoor commitments. This is by itself an important primitive and of independent interest as it appears to contradict a known impossibility result. We argue that a relaxed binding property lets us circumvent the impossibility result while still retaining the usefulness of the primitive in important applications as mentioned above.
Masayuki Abe, Markulf Kohlweiss, Miyako Ohkubo, Mehdi Tibouchi

Zero-Knowledge Proofs


Disjunctions for Hash Proof Systems: New Constructions and Applications

Hash Proof Systems were first introduced by Cramer and Shoup (Eurocrypt’02) as a tool to construct efficient chosen-ciphertext-secure encryption schemes. Since then, they have found many other applications, including password authenticated key exchange, oblivious transfer, and zero-knowledge arguments. One of the aspects that makes hash proof systems so interesting and powerful is that they can be seen as implicit proofs of membership for certain languages. As a result, by extending the family of languages that they can handle, one often obtains new applications or new ways to understand existing schemes. In this paper, we show how to construct hash proof systems for the disjunction of languages defined generically over cyclic, bilinear, and multilinear groups. Among other applications, this enables us to construct the most efficient one-time simulation-sound (quasi-adaptive) non-interactive zero-knowledge arguments for linear languages over cyclic groups, the first one-round group password-authenticated key exchange without random oracles, the most efficient threshold structure-preserving chosen- ciphertext-secure encryption scheme, and the most efficient one-round password authenticated key exchange in the UC framework.
Michel Abdalla, Fabrice Benhamouda, David Pointcheval

Quasi-Adaptive NIZK for Linear Subspaces Revisited

Non-interactive zero-knowledge (NIZK) proofs for algebraic relations in a group, such as the Groth-Sahai proofs, are an extremely powerful tool in pairing-based cryptography. A series of recent works focused on obtaining very efficient NIZK proofs for linear spaces in a weaker quasi-adaptive model. We revisit recent quasi-adaptive NIZK constructions, providing clean, simple, and improved constructions via a conceptually different approach inspired by recent developments in identity-based encryption. We then extend our techniques also to linearly homomorphic structure-preserving signatures, an object both of independent interest and with many applications.
Eike Kiltz, Hoeteck Wee

Leakage-Resilient Cryptography


Leakage-Resilient Circuits Revisited – Optimal Number of Computing Components Without Leak-Free Hardware

Side channel attacks – attacks that exploit implementation-dependent information of a cryptosystem – have been shown to be highly detrimental, and the cryptographic community has recently focused on developing techniques for securing implementations against such attacks. An important model called Only Computation Leaks (OCL) [Micali and Reyzin, TCC ’04] and its stronger variants were proposed to model a broad class of leakage attacks (a type of side-channel attack). These models allow for unbounded, arbitrary leakage as long as (1) information in each leakage observation is bounded, and (2) different parts of the computation leak independently. Various results and techniques have been developed for these models and we continue this line of research in the current work.
We address the problem of compiling any circuit into a circuit secure against OCL attacks. In order to leverage the OCL assumption, the resulting circuit will be split into components, where at any point in time only a single component is active. Optimally, we would like to output a circuit that has only one component, and no part of the computation needs to be leak-free. However, this task is impossible due to the result of Barak et al. [JACM ’12]. The current state-of-the-art constructions achieve either two components with additional leak-free hardware, or many components without leak-free hardware.
In this work, we show how to achieve the best of both worlds: We construct two-component OCL schemes without relying on leak-free components. Our approach is general and modular – we develop generic techniques to remove the hardware component from hardware-based constructions, when the functionality provided by the hardware satisfies some properties. Our techniques use universal deniable encryption (recently constructed by Sahai and Water [STOC ’14] using indistinguishable obfuscation) and non-committing encryption in a novel way. Then, we observe that the functionalities of the hardware used in previous two-component constructions of Juma and Vahlis [Crypto ’10], and Dziembowski and Faust [TCC ’12] satisfy the required properties.
The techniques developed in this paper have deep connections with adaptively secure and leakage tolerant multi-party computation (MPC). Our constructions immediately yield adaptively secure and leakage tolerant MPC protocols for any no-input randomized functionality in the semi-honest model. The result holds in the CRS model, without pre-processing. Our results also have implications to two-party leakage tolerant computation for arbitrary functionalities, which we obtain by combining our constructions with a recent result of Bitansky, Dachman-Soled, and Lin [Crypto ’14].
Dana Dachman-Soled, Feng-Hao Liu, Hong-Sheng Zhou

Noisy Leakage Revisited

Physical side-channel leakages are an important threat for cryptographic implementations. One of the most prominent countermeasures against such leakage attacks is the use of a masking scheme. A masking scheme conceals the sensitive information by randomizing intermediate values thereby making the physical leakage independent of the secret. An important practical leakage model to analyze the security of a masking scheme is the so-called noisy leakage model of Prouff and Rivain (Eurocrypt’13). Unfortunately, security proofs in the noisy leakage model require a technically involved information theoretic argument. Very recently, Duc et al. (Eurocrypt’14) showed that security in the probing model of Ishai et al. (Crypto’03) implies security in the noisy leakage model. Unfortunately, the reduction to the probing model is non-tight and requires a rather counter-intuitive growth of the amount of noise, i.e., the Prouff-Rivain bias parameter decreases proportional to the size of the set \({\mathcal X}\) of the elements that are leaking (e.g., if the leaking elements are bytes, then \(\left| {\mathcal X}\right| = 256\)). The main contribution of our work is to eliminate this non-optimality in the reduction by introducing an alternative leakage model, that we call the average probing model. We show a tight reduction between the noisy leakage model and the much simpler average random probing model; in fact, we show that these two models are essentially equivalent. We demonstrate the potential of this equivalence by two applications:
  • We show security of the additive masking scheme used in many previous works for a constant bias parameter.
  • We show that the compiler of Ishai et al. (Crypto’03) is secure in the average probing model (assuming a simple leak free component). This results into security with an optimal bias parameter of the noisy leakage for the ISW construction.
Stefan Dziembowski, Sebastian Faust, Maciej Skorski

Garbled Circuits


Privacy-Free Garbled Circuits with Applications to Efficient Zero-Knowledge

In the last few years garbled circuits (GC) have been elevated from being merely a component in Yao’s protocol for secure two-party computation, to a cryptographic primitive in its own right, following the growing number of applications that use GCs. Zero-Knowledge (ZK) protocols is one of these examples: In a recent paper Jawurek et al. [JKO13] showed that GCs can be used to construct efficient ZK proofs for unstructured languages. In this work we show that due to the property of this particular scenario (i.e., one of the parties knows all the secret input bits, and therefore all intermediate values in the computation), we can construct more efficient garbling schemes specifically tailored to this goal. As a highlight of our result, in one of our constructions only one ciphertext per gate needs to be communicated and XOR gates never require any cryptographic operations. In addition to making a step forward towards more practical ZK, we believe that our contribution is also interesting from a conceptual point of view: in the terminology of Bellare et al. [BHR12] our garbling schemes achieve authenticity, but no privacy nor obliviousness, therefore representing the first natural separation between those notions.
Tore Kasper Frederiksen, Jesper Buus Nielsen, Claudio Orlandi

Two Halves Make a Whole

Reducing Data Transfer in Garbled Circuits Using Half Gates
The well-known classical constructions of garbled circuits use four ciphertexts per gate, although various methods have been proposed to reduce this cost. The best previously known methods for optimizing AND gates (two ciphertexts; Pinkas et al., ASIACRYPT 2009) and XOR gates (zero ciphertexts; Kolesnikov and Schneider, ICALP 2008) were incompatible, so most implementations used the best known method compatible with free-XOR gates (three ciphertexts; Kolesnikov and Schneider, ICALP 2008). In this work we show how to simultaneously garble AND gates using two ciphertexts and XOR gates using zero ciphertexts, resulting in smaller garbled circuits than any prior scheme. The main idea behind our construction is to break an AND gate into two half-gates — AND gates for which one party knows one input. Each half-gate can be garbled with a single ciphertext, so our construction uses two ciphertexts for each AND gate while being compatible with free-XOR gates. The price for the reduction in size is that the evaluator must perform two cryptographic operations per AND gate, rather than one as in previous schemes. We experimentally demonstrate that our garbling scheme leads to an overall decrease in time (up to 25%), bandwidth (up to 33%), and energy use (up to 20%) over several benchmark applications. We show that our construction is optimal for a large class of garbling schemes encompassing all known practical garbling techniques.
Samee Zahur, Mike Rosulek, David Evans

Crypto Currencies


One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin

We construct a 3-move public coin special honest verifier zero-knowledge proof, a so-called Sigma-protocol, for a list of commitments having at least one commitment that opens to 0. It is not required for the prover to know openings of the other commitments. The proof system is efficient, in particular in terms of communication requiring only the transmission of a logarithmic number of commitments.
We use our proof system to instantiate both ring signatures and zerocoin, a novel mechanism for bitcoin privacy. We use our Sigma-protocol as a (linkable) ad-hoc group identification scheme where the users have public keys that are commitments and demonstrate knowledge of an opening for one of the commitments to unlinkably identify themselves (once) as belonging to the group. Applying the Fiat-Shamir transform on the group identification scheme gives rise to ring signatures, applying it to the linkable group identification scheme gives rise to zerocoin.
Our ring signatures are very small compared to other ring signature schemes and we only assume the users’ secret keys to be the discrete logarithms of single group elements so the setup is quite realistic. Similarly, compared with the original zerocoin protocol we only rely on a weak cryptographic assumption and do not require a trusted setup.
A third application of our Sigma protocol is an efficient proof of membership of a secret committed value belonging to a public list of values.
Jens Groth, Markulf Kohlweiss

The Bitcoin Backbone Protocol: Analysis and Applications

Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two of its fundamental properties which we call common prefix and chain quality in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the “hashing power” of the adversary relative to network synchronicity; we show our results to be tight under high synchronization.
Next, we propose and analyze applications that can be built “on top” of the backbone protocol, specifically focusing on Byzantine agreement (BA) and on the notion of a public transaction ledger. Regarding BA, we observe that Nakamoto’s suggestion falls short of solving it, and present a simple alternative which works assuming that the adversary’s hashing power is bounded by \(1/3\). The public transaction ledger captures the essence of Bitcoin’s operation as a cryptocurrency, in the sense that it guarantees the liveness and persistence of committed transactions. Based on this notion we describe and analyze the Bitcoin system as well as a more elaborate BA protocol, proving them secure assuming high network synchronicity and that the adversary’s hashing power is strictly less than \(1/2\), while the adversarial bound needed for security decreases as the network desynchronizes.
Juan Garay, Aggelos Kiayias, Nikos Leonardos

Secret Sharing


Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions

We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy property of the resulting secret sharing scheme essentially becomes independent of the code we use, only depending on its rate. This allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or efficient list-decoding. Choosing the error correcting codes and universal hash functions involved carefully, we obtain solutions to the following open problems:
  • A linear near-threshold secret sharing scheme with both linear time sharing and reconstruction algorithms and large secrets (i.e. secrets of size \(\Omega (n)\)). Thus, the computational overhead per shared bit in this scheme is constant.
  • An efficiently reconstructible robust secret sharing scheme for \(n/3 \le t < (1 - \epsilon ) \cdot n/2\) corrupted players (for any constant \(\epsilon > 0\)) with shares of optimal size \(O(1 + \lambda / n)\) and secrets of size \(\Omega (n + \lambda )\), where \(\lambda \) is the security parameter.
Ronald Cramer, Ivan Bjerre Damgård, Nico Döttling, Serge Fehr, Gabriele Spini

Function Secret Sharing

Motivated by the goal of securely searching and updating distributed data, we introduce and study the notion of function secret sharing (FSS). This new notion is a natural generalization of distributed point functions (DPF), a primitive that was recently introduced by Gilboa and Ishai (Eurocrypt 2014). Given a positive integer \(p\ge 2\) and a class \(\mathcal F\) of functions \(f:\{0,1\}^n\rightarrow \mathbb G\), where \(\mathbb G\) is an Abelian group, a \(p\)-party FSS scheme for \(\mathcal F\) allows one to split each \(f\in \mathcal F\) into \(p\) succinctly described functions \(f_i:\{0,1\}^n\rightarrow \mathbb G\), \(1\le i\le p\), such that: (1) \(\sum _{i=1}^p f_i=f\), and (2) any strict subset of the \(f_i\) hides \(f\). Thus, an FSS for \(\mathcal F\) can be thought of as method for succinctly performing an “additive secret sharing” of functions from \(\mathcal F\). The original definition of DPF coincides with a two-party FSS for the class of point functions, namely the class of functions that have a nonzero output on at most one input.
We present two types of results. First, we obtain efficiency improvements and extensions of the original DPF construction. Then, we initiate a systematic study of general FSS, providing some constructions and establishing relations with other cryptographic primitives. More concretely, we obtain the following main results:
  • Improved DPF. We present an improved (two-party) DPF construction from a pseudorandom generator (PRG), reducing the length of the key describing each \(f_i\) from \(O(\lambda \cdot n^{\log _23})\) to \(O(\lambda n)\), where \(\lambda \) is the PRG seed length.
  • Multi-party DPF. We present the first nontrivial construction of a \(p\)-party DPF for \(p\ge 3\), obtaining a near-quadratic improvement over a naive construction that additively shares the truth-table of \(f\). This constrcution too can be based on any PRG.
  • FSS for simple functions. We present efficient PRG-based FSS constructions for natural function classes that extend point functions, including interval functions and partial matching functions.
  • A study of general FSS. We show several relations between general FSS and other cryptographic primitives. These include a construction of general FSS via obfuscation, an indication for the implausibility of constructing general FSS from weak cryptographic assumptions such as the existence of one-way functions, a completeness result, and a relation with pseudorandom functions.
Elette Boyle, Niv Gilboa, Yuval Ishai

Outsourcing Computations


Cluster Computing in Zero Knowledge

Large computations, when amenable to distributed parallel execution, are often executed on computer clusters, for scalability and cost reasons. Such computations are used in many applications, including, to name but a few, machine learning, webgraph mining, and statistical machine translation. Oftentimes, though, the input data is private and only the result of the computation can be published. Zero-knowledge proofs would allow, in such settings, to verify correctness of the output without leaking (additional) information about the input.
In this work, we investigate theoretical and practical aspects of zero-knowledge proofs for cluster computations. We design, build, and evaluate zero-knowledge proof systems for which: (i) a proof attests to the correct execution of a cluster computation; and (ii) generating the proof is itself a cluster computation that is similar in structure and complexity to the original one. Concretely, we focus on MapReduce, an elegant and popular form of cluster computing.
Previous zero-knowledge proof systems can in principle prove a MapReduce computation’s correctness, via a monolithic NP statement that reasons about all mappers, all reducers, and shuffling. However, it is not clear how to generate the proof for such monolithic statements via parallel execution by a distributed system. Our work demonstrates, by theory and implementation, that proof generation can be similar in structure and complexity to the original cluster computation.
Our main technique is a bootstrapping theorem for succinct non-interactive arguments of knowledge (SNARKs) that shows how, via recursive proof composition and Proof-Carrying Data, it is possible to transform any SNARK into a distributed SNARK for MapReduce which proves, piecewise and in a distributed way, the correctness of every step in the original MapReduce computation as well as their global consistency.
Alessandro Chiesa, Eran Tromer, Madars Virza

Hosting Services on an Untrusted Cloud

We consider a scenario where a service provider has created a software service \(S\) and desires to outsource the execution of this service to an untrusted cloud. The software service contains secrets that the provider would like to keep hidden from the cloud. For example, the software might contain a secret database, and the service could allow users to make queries to different slices of this database depending on the user’s identity.
This setting presents significant challenges not present in previous works on outsourcing or secure computation. Because secrets in the software itself must be protected against an adversary that has full control over the cloud that is executing this software, our notion implies indistinguishability obfuscation. Furthermore, we seek to protect knowledge of the software \(S\) to the maximum extent possible even if the cloud can collude with several corrupted users.
In this work, we provide the first formalizations of security for this setting, yielding our definition of a secure cloud service scheme. We provide constructions of secure cloud service schemes assuming indistinguishability obfuscation, one-way functions, and non-interactive zero-knowledge proofs.
At the heart of our paper are novel techniques to allow parties to simultaneously authenticate and securely communicate with an obfuscated program, while hiding this authentication and communication from the entity in possession of the obfuscated program.
Dan Boneh, Divya Gupta, Ilya Mironov, Amit Sahai

Obfuscation and E-Voting


How to Obfuscate Programs Directly

We propose a new way to obfuscate programs, via composite-order multilinear maps. Our construction operates directly on straight-line programs (arithmetic circuits), rather than converting them to matrix branching programs as in other known approaches. This yields considerable efficiency improvements. For an NC\(^1\) circuit of size \(s\) and depth \(d\), with \(n\) inputs, we require only \(O(d^2s^2 + n^2)\) multilinear map operations to evaluate the obfuscated circuit—as compared with other known approaches, for which the number of operations is exponential in \(d\). We prove virtual black-box (VBB) security for our construction in a generic model of multilinear maps of hidden composite order, extending previous models for the prime-order setting.
Our scheme works either with “noisy” multilinear maps, which can only evaluate expressions of degree \(\lambda ^c\) for pre-specified constant \(c\); or with “clean” multilinear maps, which can evaluate arbitrary expressions. With “noisy” maps, our new obfuscator applies only to NC\(^1\) circuits, requiring the additional assumption of FHE in order to bootstrap to P/poly (as in other obfuscation constructions). From “clean” multilinear maps, on the other hand (whose existence is still open), we present the first approach that would achieve obfuscation for P/poly directly, without FHE.
Our construction is efficient enough that if “clean” multilinear maps were known, then general-purpose program obfuscation could become implementable in practice. Our results demonstrate that the question of “clean” multilinear maps is not a technicality, but a central open problem.
Joe Zimmerman

End-to-End Verifiable Elections in the Standard Model

We present the cryptographic implementation of “DEMOS”, a new e-voting system that is end-to-end verifiable in the standard model, i.e., without any additional “setup” assumption or access to a random oracle (RO). Previously known end-to-end verifiable e-voting systems required such additional assumptions (specifically, either the existence of a “randomness beacon” or were only shown secure in the RO model). In order to analyze our scheme, we also provide a modeling of end-to-end verifiability as well as privacy and receipt-freeness that encompasses previous definitions in the form of two concise attack games.
Our scheme satisfies end-to-end verifiability information theoretically in the standard model and privacy/receipt-freeness under a computational assumption (subexponential Decisional Diffie Helman). In our construction, we utilize a number of techniques used for the first time in the context of e-voting schemes that include utilizing randomness from bit-fixing sources, zero-knowledge proofs with imperfect verifier randomness and complexity leveraging.
Aggelos Kiayias, Thomas Zacharias, Bingsheng Zhang

Multi-party Computations


Cryptographic Agents: Towards a Unified Theory of Computing on Encrypted Data

We provide a new framework of cryptographic agents that unifies various modern “cryptographic objects” — identity-based encryption, fully-homomorphic encryption, functional encryption, and various forms of obfuscation – similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs. These cryptographic objects can all be cleanly modeled as “schemata” in our framework.
Highlights of our framework include the following:
  • We use a new indistinguishability preserving (IND-PRE) definition of security that interpolates indistinguishability and simulation style definitions, which (often) sidesteps the known impossibilities for the latter. IND-PRE-security is parameterized by the choice of the “test” family, such that by choosing different test families, one can obtain different levels of security for the same primitive (including various standard definitions in the literature).
  • We present a notion of reduction from one schema to another and a powerful composition theorem with respect to \(\mathsf{IND-PRE }\) security. We show that obfuscation is a “complete” schema under this notion, under standard cryptographic assumptions. We also provide a stricter notion of reduction (\(\varDelta \)-reduction) that composes even when security is only with respect to certain restricted test families of importance.
  • Last but not the least, our framework can be used to model abstractions like the generic group model and the random oracle model, letting one translate a general class of constructions in these heuristic models to constructions based on standard model assumptions.
We also illustrate how our framework can be applied to specific primitives like obfuscation and functional encryption. We relate our definitions to existing definitions and also give new constructions and reductions between different primitives.
Shashank Agrawal, Shweta Agrawal, Manoj Prabhakaran

Executable Proofs, Input-Size Hiding Secure Computation and a New Ideal World

In STOC 1987, Goldreich, Micali and Wigderson [GMW87] proved a fundamental result: it is possible to securely evaluate any function. Their security formulation consisted of transforming a real-world adversary into an ideal-world one and became a de facto standard for assessing security of protocols.
In this work we propose a new approach for the ideal world. Our new definition preserves the unconditional security of ideal-world executions and follows the spirit of the real/ideal world paradigm. Moreover we show that our definition is equivalent to that of [GMW87] when the input size is public, thus it is a strict generalization of [GMW87].
In addition, we prove that our new formulation is useful by showing that it allows the construction of protocols for input-size hiding secure two-party computation for any two-party functionality under standard assumptions and secure against malicious adversaries. More precisely we show that in our model, in addition to securely evaluating every two-party functionality, one can also protect the input-size privacy of one of the two players. Such an input-size hiding property is not implied by the standard definitions for two-party computation and is not satisfied by known constructions for secure computation. This positively answers a question posed by [LNO13] and  [CV12]. Finally, we show that obtaining such a security notion under a more standard definition (one with a more traditional ideal world) would imply a scheme for “proofs of polynomial work”, a primitive that seems unlikely to exist under standard assumptions.
Along the way, we will introduce the notion of “executable proof”, which will be used in our ideal-world formulation and may be of independent interest.
Melissa Chase, Rafail Ostrovsky, Ivan Visconti



Semantically Secure Order-Revealing Encryption: Multi-input Functional Encryption Without Obfuscation

Deciding “greater-than” relations among data items just given their encryptions is at the heart of search algorithms on encrypted data, most notably, non-interactive binary search on encrypted data. Order-preserving encryption provides one solution, but provably provides only limited security guarantees. Two-input functional encryption is another approach, but requires the full power of obfuscation machinery and is currently not implementable.
We construct the first implementable encryption system supporting greater-than comparisons on encrypted data that provides the “best-possible” semantic security. In our scheme there is a public algorithm that given two ciphertexts as input, reveals the order of the corresponding plaintexts and nothing else. Our constructions are inspired by obfuscation techniques, but do not use obfuscation. For example, to compare two 16-bit encrypted values (e.g., salaries or age) we only need a 9-way multilinear map. More generally, comparing \(k\)-bit values requires only a \((k/2+1)\)-way multilinear map. The required degree of multilinearity can be further reduced, but at the cost of increasing ciphertext size.
Beyond comparisons, our results give an implementable secret-key multi-input functional encryption scheme for functionalities that can be expressed as (generalized) branching programs of polynomial length and width. Comparisons are a special case of this class, where for \(k\)-bit inputs the branching program is of length \(k+1\) and width \(4\).
Dan Boneh, Kevin Lewi, Mariana Raykova, Amit Sahai, Mark Zhandry, Joe Zimmerman

Improved Dual System ABE in Prime-Order Groups via Predicate Encodings

We present a modular framework for the design of efficient adaptively secure attribute-based encryption (ABE) schemes for a large class of predicates under the standard \(k\)-Lin assumption in prime-order groups; this is the first uniform treatment of dual system ABE across different predicates and across both composite and prime-order groups. Via this framework, we obtain concrete efficiency improvements for several ABE schemes. Our framework has three novel components over prior works: (i) new techniques for simulating composite-order groups in prime-order ones, (ii) a refinement of prior encodings framework for dual system ABE in composite-order groups, (iii) an extension to weakly attribute-hiding predicate encryption (which includes anonymous identity-based encryption as a special case).
Jie Chen, Romain Gay, Hoeteck Wee

Resistant Protocols


Resisting Randomness Subversion: Fast Deterministic and Hedged Public-Key Encryption in the Standard Model

This paper provides the first efficient, standard-model, fully-secure schemes for some related and challenging forms of public-key encryption (PKE), namely deterministic and hedged PKE. These forms of PKE defend against subversion of random number generators, an end given new urgency by recent revelations on the nature and extent of such subversion.We resolve the (recognized) technical challenges in reaching these goals via a new paradigm that combines UCEs (universal computational extractors) with LTDFs (lossy trapdoor functions). Crucially, we rely only on a weak form of UCE, namely security for statistically (rather than computationally) unpredictable sources. We then define and achieve unique-ciphertext PKE as a way to defend against implementation subversion via algorithm-substitution attacks.
Mihir Bellare, Viet Tung Hoang

Cryptographic Reverse Firewalls

Recent revelations by Edward Snowden [3, 20, 27] show that a user’s own hardware and software can be used against her in various ways (e.g., to leak her private information). And, a series of recent announcements has shown that widespread implementations of cryptographic software often contain serious bugs that cripple security (e.g., [1214, 22]). This motivates us to consider the following (seemingly absurd) question: How can we guarantee a user’s security when she may be using a malfunctioning or arbitrarily compromised machine? To that end, we introduce the notion of a cryptographic reverse firewall (RF). Such a machine sits between the user’s computer and the outside world, potentially modifying the messages that she sends and receives as she engages in a cryptographic protocol.
A good reverse firewall accomplishes three things: (1) it maintains functionality, so that if the user’s computer is working correctly, the RF will not break the functionality of the underlying protocol; (2) it preserves security, so that regardless of how the user’s machine behaves, the presence of the RF will provide the same security guarantees as the properly implemented protocol; and (3) it resists exfiltration, so that regardless of how the user’s machine behaves, the presence of the RF will prevent the machine from leaking any information to the outside world. Importantly, we do not model the firewall as a trusted party. It does not share any secrets with the user, and the protocol should be both secure and functional without the firewall (when the protocol’s implementation is correct).
Our security definition for reverse firewalls depends on the security notion(s) of the underlying protocol. As such, our model generalizes much prior work (e.g., [5, 7, 26, 32]) and provides a general framework for building cryptographic schemes that remain secure when run on compromised machine. It is also a modern take on a line of work that received considerable attention in the 80s and 90s (e.g., [7, 9, 11, 15, 16, 30, 31]).
We show that our definition is achievable by constructing a private function evaluation protocol with a secure reverse firewall for each party. Along the way, we design an oblivious transfer protocol that also has a secure RF for each party, and a rerandomizable garbled circuit that is both more efficient and more secure than previous constructions. Finally, we show how to convert any protocol into a protocol with an exfiltration-resistant reverse firewall for all parties. (In other words, we provide a generic way to prevent a tampered machine from leaking information to an eavesdropper via any protocol.)
Ilya Mironov, Noah Stephens-Davidowitz

Key Exchange


Mind the Gap: Modular Machine-Checked Proofs of One-Round Key Exchange Protocols

Using EasyCrypt, we formalize a new modular security proof for one-round authenticated key exchange protocols in the random oracle model. Our proof improves earlier work by Kudla and Paterson (ASIACRYPT 2005) in three significant ways: we consider a stronger adversary model, we provide support tailored to protocols that utilize the \(\mathsf {Naxos}\) trick, and we support proofs under the Computational DH assumption not relying on Gap oracles. Furthermore, our modular proof can be used to obtain concrete security proofs for protocols with or without adversarial key registration. We use this support to investigate, still using EasyCrypt, the connection between proofs without Gap assumptions and adversarial key registration. For the case of honestly generated keys, we obtain the first proofs of the \(\mathsf {Naxos}\) and \(\mathsf {Nets}\) protocols under the Computational DH assumption. For the case of adversarial key registration, we obtain machine-checked and modular variants of the well-known proofs for \(\mathsf {Naxos}\), \(\mathsf {Nets}\), and \(\mathsf Naxos \text {}\)+.
Gilles Barthe, Juan Manuel Crespo, Yassine Lakhnech, Benedikt Schmidt

Authenticated Key Exchange from Ideal Lattices

In this paper, we present a practical and provably secure two-pass authenticated key exchange protocol over ideal lattices, which is conceptually simple and has similarities to the Diffie-Hellman based protocols such as HMQV (CRYPTO 2005) and OAKE (CCS 2013). Our method does not involve other cryptographic primitives—in particular, it does not use signatures—which simplifies the protocol and enables us to base the security directly on the hardness of the ring learning with errors problem. The security is proven in the Bellare-Rogaway model with weak perfect forward secrecy in the random oracle model. We also give a one-pass variant of our two-pass protocol, which might be appealing in specific applications. Several concrete choices of parameters are provided, and a proof-of-concept implementation shows that our protocols are indeed practical.
Jiang Zhang, Zhenfeng Zhang, Jintai Ding, Michael Snook, Özgür Dagdelen

Quantum Cryptography


Non-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model

We present a construction for non-interactive zero-knowledge proofs of knowledge in the random oracle model from general sigma-protocols. Our construction is secure against quantum adversaries. Prior constructions (by Fiat-Shamir and by Fischlin) are only known to be secure against classical adversaries, and Ambainis, Rosmanis, Unruh (FOCS 2014) gave evidence that those constructions might not be secure against quantum adversaries in general.
To prove security of our constructions, we additionally develop new techniques for adaptively programming the quantum random oracle.
Dominique Unruh

Privacy Amplification in the Isolated Qubits Model

Isolated qubits are a special class of quantum devices, which can be used to implement tamper-resistant cryptographic hardware such as one-time memories (OTM’s). Unfortunately, these OTM constructions leak some information, and standard methods for privacy amplification cannot be applied here, because the adversary has advance knowledge of the hash function that the honest parties will use.
In this paper we show a stronger form of privacy amplification that solves this problem, using a fixed hash function that is secure against all possible adversaries in the isolated qubits model. This allows us to construct single-bit OTM’s which only leak an exponentially small amount of information.
We then study a natural generalization of the isolated qubits model, where the adversary is allowed to perform a polynomially-bounded number of entangling gates, in addition to unbounded local operations and classical communication (LOCC). We show that our technique for privacy amplification is also secure in this setting.
Yi-Kai Liu

Discrete Logarithms


Generic Hardness of the Multiple Discrete Logarithm Problem

We study generic hardness of the multiple discrete logarithm problem, where the solver has to solve \(n\) instances of the discrete logarithm problem simultaneously. There are known generic algorithms which perform \(O(\sqrt{np})\) group operations, where \(p\) is the group order, but no generic lower bound was known other than the trivial bound. In this paper we prove the tight generic lower bound, showing that the previously known algorithms are asymptotically optimal. We establish the lower bound by studying hardness of a related computational problem which we call the search-by-hyperplane-queries problem, which may be of independent interest.
Aaram Yun


Weitere Informationen

Premium Partner