Functional Encryption

Frontmatter

Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks

Abstract

We construct a functional encryption scheme for circuits which simultaneously achieves and improves upon the security of the current best known, and incomparable, constructions from standard assumptions: reusable garbled circuits by Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (STOC 2013) [GKP+13] and predicate encryption for circuits by Gorbunov, Vaikuntanathan and Wee (CRYPTO 2015) [GVW15]. Our scheme is secure based on the learning with errors (LWE) assumption. Our construction implies:

1.

A new construction for reusable garbled circuits that achieves stronger security than the only known prior construction [GKP+13].

2.

A new construction for bounded collusion functional encryption with substantial efficiency benefits: our public parameters and ciphertext size incur an additive growth of \(O(Q^2)\), where Q is the number of permissible queries (We note that due to a lower bound [AGVW13], the ciphertext size must necessarily grow with Q). Additionally, the ciphertext of our scheme is succinct, in that it does not depend on the size of the circuit. By contrast, the prior best construction [GKP+13, GVW12] incurred a multiplicative blowup of \(O(Q^4)\) in both the public parameters and ciphertext size. However, our scheme is secure in a weaker game than [GVW12].

Additionally, we show that existing LWE based predicate encryption schemes [AFV11, GVW15] are completely insecure against a general functional encryption adversary (i.e. in the “strong attribute hiding” game). We demonstrate three different attacks, the strongest of which is applicable even to the inner product predicate encryption scheme [AFV11]. Our attacks are practical and allow the attacker to completely recover \(\mathbf {x}\) from its encryption \(\mathsf{Enc}(\mathbf {x})\) within a polynomial number of queries. This illustrates that the barrier between predicate and functional encryption is not just a limitation of proof techniques. We believe these attacks shed significant light on the barriers to achieving full fledged functional encryption from LWE, even for simple functionalities such as inner product zero testing [KSW08, AFV11].

Along the way, we develop a new proof technique that permits the simulator to program public parameters based on keys that will be requested in the future. This technique may be of independent interest.

Shweta Agrawal

Generic Transformations of Predicate Encodings: Constructions and Applications

Abstract

Predicate encodings (Wee, TCC 2014; Chen, Gay, Wee, EUROCRYPT 2015), are symmetric primitives that can be used for building predicate encryption schemes. We give an algebraic characterization of the notion of privacy from predicate encodings, and explore several of its consequences. Specifically, we propose more efficient predicate encodings for boolean formulae and arithmetic span programs, and generic optimizations of predicate encodings. We define new constructions to build boolean combination of predicate encodings. We formalize the relationship between predicate encodings and pair encodings (Attrapadung, EUROCRYPT 2014), another primitive that can be transformed generically into predicate encryption schemes, and compare our constructions for boolean combinations of pair encodings with existing similar constructions from pair encodings. Finally, we demonstrate that our results carry to tag-based encodings (Kim, Susilo, Guo, and Au, SCN 2016).

Miguel Ambrona, Gilles Barthe, Benedikt Schmidt

Practical Functional Encryption for Quadratic Functions with Applications to Predicate Encryption

Abstract

We present two practically efficient functional encryption schemes for a large class of quadratic functionalities. Specifically, our constructions enable the computation of so-called bilinear maps on encrypted vectors. This represents a practically relevant class of functions that includes, for instance, multivariate quadratic polynomials (over the integers). Our realizations work over asymmetric bilinear groups and are surprisingly efficient and easy to implement. For instance, in our most efficient scheme the public key and each ciphertext consist of \(2n+1\) and \(4n+2\) group elements respectively, where n is the dimension of the encrypted vectors, while secret keys are only two group elements. Our two schemes build on similar ideas, but develop them in a different way in order to achieve distinct goals. Our first scheme is proved (selectively) secure under standard assumptions, while our second construction is concretely more efficient and is proved (adaptively) secure in the generic group model.

As a byproduct of our functional encryption schemes, we show new predicate encryption schemes for degree-two polynomial evaluation, where ciphertexts consist of only O(n) group elements. This significantly improves the \(O(n^2)\) bound one would get from inner product encryption-based constructions.

Carmen Elisabetta Zaira Baltico, Dario Catalano, Dario Fiore, Romain Gay

Foundations I

Frontmatter

Memory-Tight Reductions

Abstract

Cryptographic reductions typically aim to be tight by transforming an adversary \(\mathsf{A}\) into an algorithm that uses essentially the same resources as \(\mathsf{A}\). In this work we initiate the study of memory efficiency in reductions. We argue that the amount of working memory used (relative to the initial adversary) is a relevant parameter in reductions, and that reductions that are inefficient with memory will sometimes yield less meaningful security guarantees. We then point to several common techniques in reductions that are memory-inefficient and give a toolbox for reducing memory usage. We review common cryptographic assumptions and their sensitivity to memory usage. Finally, we prove an impossibility result showing that reductions between some assumptions must unavoidably be either memory- or time-inefficient. This last result follows from a connection to data streaming algorithms for which unconditional memory lower bounds are known.

Benedikt Auerbach, David Cash, Manuel Fersch, Eike Kiltz

Be Adaptive, Avoid Overcommitting

Abstract

For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future.

Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to \(2^n\). However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of \(m \ll n\) bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only \(2^m \ll 2^n\).

In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.

Zahra Jafargholi, Chethan Kamath, Karen Klein, Ilan Komargodski, Krzysztof Pietrzak, Daniel Wichs

Two-Party Computation

Frontmatter

The TinyTable Protocol for 2-Party Secure Computation, or: Gate-Scrambling Revisited

Abstract

We propose a new protocol, nicknamed TinyTable, for maliciously secure 2-party computation in the preprocessing model. One version of the protocol is useful in practice and allows, for instance, secure AES encryption with latency about 1 ms and amortized time about 0.5 \(\upmu \)s per AES block on a fast cloud set-up. Another version is interesting from a theoretical point of view: we achieve a maliciously and unconditionally secure 2-party protocol in the preprocessing model for computing a Boolean circuit, where both the communication complexity and preprocessed data size needed is O(s) where s is the circuit size, while the computational complexity is \(O(k^\epsilon s)\) where k is the statistical security parameter and \(\epsilon <1\) is a constant. For general circuits with no assumption on their structure, this is the best asymptotic performance achieved so far in this model.

Ivan Damgård, Jesper Buus Nielsen, Michael Nielsen, Samuel Ranellucci

Privacy-Free Garbled Circuits for Formulas: Size Zero and Information-Theoretic

Abstract

Garbled circuits are of central importance in cryptography, finding widespread application in secure computation, zero-knowledge (ZK) protocols, and verifiable outsourcing of computation to name a few. We are interested in a particular kind of garbling scheme, termed privacy-free in the literature. We show that Boolean formulas can be garbled information-theoretically in the privacy-free setting, producing no ciphertexts at all. Existing garbling schemes either rely on cryptographic assumptions (and thus require cryptographic operations to construct and evaluate garbled circuits), produce garbled circuits of non-zero size, or are restricted to low depth formulaic circuits. Our result has both theoretical and practical implications for garbled circuits as a primitive. On the theory front, our result breaks the known theoretical lower bound of one ciphertext for garbling an AND gate in this setting. As an interesting implication of producing size zero garbled circuits, our scheme scores adaptive security for free. On the practical side, our garbling scheme involves only cheap XOR operations and produces size zero garbled circuits. As a side result, we propose several interesting extensions of our scheme. Namely, we show how to garble threshold and high fan-in gates.

An aspect of our garbling scheme that we believe is of theoretical interest is that it does not maintain the invariant that the garbled circuit evaluator must not at any point be in possession of both keys of any wire in the garbled circuit.

Our scheme directly finds application in ZK protocols where the verification function of the language is representable by a formulaic circuit. Such examples include Boolean formula satisfiability. The ZK protocols obtained by plugging in our scheme in the known paradigm of building ZK protocols from garbled circuits offer better proof size, while relying on standard assumptions. Furthermore, the adaptivity of our garbling scheme allows us to cast our ZK protocols in the offline-online setting and offload circuit dependent communication and computation to the offline phase. As a result, the online phase enjoys communication and computation (in terms of number of symmetric key operations) complexity that are linearly proportional to the witness size alone.

Yashvanth Kondi, Arpita Patra

Secure Arithmetic Computation with Constant Computational Overhead

Abstract

We study the complexity of securely evaluating an arithmetic circuit over a finite field \(\mathbb {F}\) in the setting of secure two-party computation with semi-honest adversaries. In all existing protocols, the number of arithmetic operations per multiplication gate grows either linearly with \(\log |\mathbb {F}|\) or polylogarithmically with the security parameter. We present the first protocol that only makes a constant (amortized) number of field operations per gate. The protocol uses the underlying field \(\mathbb {F}\) as a black box, and its security is based on arithmetic analogues of well-studied cryptographic assumptions.

Our protocol is particularly appealing in the special case of securely evaluating a “vector-OLE” function of the form \(\varvec{a}x+\varvec{b}\), where \(x\in \mathbb {F}\) is the input of one party and \(\varvec{a},\varvec{b}\in \mathbb {F}^w\) are the inputs of the other party. In this case, which is motivated by natural applications, our protocol can achieve an asymptotic rate of 1/3 (i.e., the communication is dominated by sending roughly 3w elements of \(\mathbb {F}\)). Our implementation of this protocol suggests that it outperforms competing approaches even for relatively small fields \(\mathbb {F}\) and over fast networks.

Our technical approach employs two new ingredients that may be of independent interest. First, we present a general way to combine any linear code that has a fast encoder and a cryptographic (“LPN-style”) pseudorandomness property with another linear code that supports fast encoding and erasure-decoding, obtaining a code that inherits both the pseudorandomness feature of the former code and the efficiency features of the latter code. Second, we employ local arithmetic pseudo-random generators, proposing arithmetic generalizations of boolean candidates that resist all known attacks.

Benny Applebaum, Ivan Damgård, Yuval Ishai, Michael Nielsen, Lior Zichron

Encryption Switching Protocols Revisited: Switching Modulo p

Abstract

At CRYPTO 2016, Couteau, Peters and Pointcheval introduced a new primitive called encryption switching protocols, allowing to switch ciphertexts between two encryption schemes. If such an ESP is built with two schemes that are respectively additively and multiplicatively homomorphic, it naturally gives rise to a secure 2-party computation protocol. It is thus perfectly suited for evaluating functions, such as multivariate polynomials, given as arithmetic circuits. Couteau et al. built an ESP to switch between Elgamal and Paillier encryptions which do not naturally fit well together. Consequently, they had to design a clever variant of Elgamal over \(\mathbf {Z}/n\mathbf {Z}\) with a costly shared decryption.

In this paper, we first present a conceptually simple generic construction for encryption switching protocols. We then give an efficient instantiation of our generic approach that uses two well-suited protocols, namely a variant of Elgamal in \(\mathbf {Z}/p\mathbf {Z}\) and the Castagnos-Laguillaumie encryption which is additively homomorphic over \(\mathbf {Z}/p\mathbf {Z}\). Among other advantages, this allows to perform all computations modulo a prime p instead of an RSA modulus. Overall, our solution leads to significant reductions in the number of rounds as well as the number of bits exchanged by the parties during the interactive protocols. We also show how to extend its security to the malicious setting.

Guilhem Castagnos, Laurent Imbert, Fabien Laguillaumie

Bitcoin

Frontmatter

The Bitcoin Backbone Protocol with Chains of Variable Difficulty

Abstract

Bitcoin’s innovative and distributedly maintained blockchain data structure hinges on the adequate degree of difficulty of so-called “proofs of work,” which miners have to produce in order for transactions to be inserted. Importantly, these proofs of work have to be hard enough so that miners have an opportunity to unify their views in the presence of an adversary who interferes but has bounded computational power, but easy enough to be solvable regularly and enable the miners to make progress. As such, as the miners’ population evolves over time, so should the difficulty of these proofs. Bitcoin provides this adjustment mechanism, with empirical evidence of a constant block generation rate against such population changes.

In this paper we provide the first formal analysis of Bitcoin’s target (re)calculation function in the cryptographic setting, i.e., against all possible adversaries aiming to subvert the protocol’s properties. We extend the q-bounded synchronous model of the Bitcoin backbone protocol [Eurocrypt 2015], which posed the basic properties of Bitcoin’s underlying blockchain data structure and shows how a robust public transaction ledger can be built on top of them, to environments that may introduce or suspend parties in each round.

We provide a set of necessary conditions with respect to the way the population evolves under which the “Bitcoin backbone with chains of variable difficulty” provides a robust transaction ledger in the presence of an actively malicious adversary controlling a fraction of the miners strictly below \(50\%\) at each instant of the execution. Our work introduces new analysis techniques and tools to the area of blockchain systems that may prove useful in analyzing other blockchain protocols.

Juan Garay, Aggelos Kiayias, Nikos Leonardos

Bitcoin as a Transaction Ledger: A Composable Treatment

Abstract

Bitcoin is one of the most prominent examples of a distributed cryptographic protocol that is extensively used in reality. Nonetheless, existing security proofs are property-based, and as such they do not support composition.

In this work we put forth a universally composable treatment of the Bitcoin protocol. We specify the goal that Bitcoin aims to achieve as a ledger functionality in the (G)UC model of Canetti et al. [TCC’07]. Our ledger functionality is weaker than the one recently proposed by Kiayias, Zhou, and Zikas [EUROCRYPT’16], but unlike the latter suggestion, which is arguably not implementable given the Bitcoin assumptions, we prove that the one proposed here is securely UC realized under standard assumptions by an appropriate abstraction of Bitcoin as a UC protocol. We further show how known property-based approaches can be cast as special instances of our treatment and how their underlying assumptions can be cast in (G)UC without restricting the environment or the adversary.

Christian Badertscher, Ueli Maurer, Daniel Tschudi, Vassilis Zikas

Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol

Abstract

We present “Ouroboros”, the first blockchain protocol based on proof of stake with rigorous security guarantees. We establish security properties for the protocol comparable to those achieved by the bitcoin blockchain protocol. As the protocol provides a “proof of stake” blockchain discipline, it offers qualitative efficiency advantages over blockchains based on proof of physical resources (e.g., proof of work). We also present a novel reward mechanism for incentivizing Proof of Stake protocols and we prove that, given this mechanism, honest behavior is an approximate Nash equilibrium, thus neutralizing attacks such as selfish mining.

Aggelos Kiayias, Alexander Russell, Bernardo David, Roman Oliynykov

Multiparty Computation

Frontmatter

Robust Non-interactive Multiparty Computation Against Constant-Size Collusion

Abstract

Non-Interactive Multiparty Computations (Beimel et al., Crypto 2014) is a very powerful notion equivalent (under some corruption model) to garbled circuits, Private Simultaneous Messages protocols, and obfuscation. We present robust solutions to the problem of Non-Interactive Multiparty Computation in the computational and information-theoretic models. Our results include the first efficient and robust protocols to compute any function in \(NC^1\) for constant-size collusions, in the information-theoretic setting and in the computational setting, to compute any function in P for constant-size collusions, assuming the existence of one-way functions. Our constructions start from a Private Simultaneous Messages construction (Feige, Killian Naor, STOC 1994 and Ishai, Kushilevitz, ISTCS 1997) and transform it into a Non-Interactive Multiparty Computation for constant-size collusions.

We also present a new Non-Interactive Multiparty Computation protocol for symmetric functions with significantly better communication complexity compared to the only known one of Beimel et al.

Fabrice Benhamouda, Hugo Krawczyk, Tal Rabin

The Price of Low Communication in Secure Multi-party Computation

Abstract

Traditional protocols for secure multi-party computation among n parties communicate at least a linear (in n) number of bits, even when computing very simple functions. In this work we investigate the feasibility of protocols with sublinear communication complexity. Concretely, we consider two clients, one of which may be corrupted, who wish to perform some “small” joint computation using n servers but without any trusted setup. We show that enforcing sublinear communication complexity drastically affects the feasibility bounds on the number of corrupted parties that can be tolerated in the setting of information-theoretic security.

We provide a complete investigation of security in the presence of semi-honest adversaries—static and adaptive, with and without erasures—and initiate the study of security in the presence of malicious adversaries. For semi-honest static adversaries, our bounds essentially match the corresponding bounds when there is no communication restriction—i.e., we can tolerate up to \(t < (1/2 -\epsilon )n\) corrupted parties. For the adaptive case, however, the situation is different. We prove that without erasures even a small constant fraction of corruptions is intolerable, and—more surprisingly—when erasures are allowed, we prove that \(t < (1 - \sqrt{0.5} - \epsilon )n\) corruptions can be tolerated, which we also show to be essentially optimal. The latter optimality proof hinges on a new treatment of probabilistic adversary structures that may be of independent interest. In the case of active corruptions in the sublinear communication setting, we prove that static “security with abort” is feasible when \(t < (1/2 - \epsilon )n\), namely, the bound that is tight for semi-honest security. All of our negative results in fact rule out protocols with sublinear message complexity.

Juan Garay, Yuval Ishai, Rafail Ostrovsky, Vassilis Zikas

Topology-Hiding Computation on All Graphs

Abstract

A distributed computation in which nodes are connected by a partial communication graph is called topology-hiding if it does not reveal information about the graph beyond what is revealed by the output of the function. Previous results have shown that topology-hiding computation protocols exist for graphs of constant degree and logarithmic diameter in the number of nodes [Moran-Orlov-Richelson, TCC’15; Hirt et al., Crypto’16] as well as for other graph families, such as cycles, trees, and low circumference graphs [Akavia-Moran, Eurocrypt’17], but the feasibility question for general graphs was open.

In this work we positively resolve the above open problem: we prove that topology-hiding MPC is feasible for all graphs under the Decisional Diffie-Hellman assumption.

Our techniques employ random-walks to generate paths covering the graph, upon which we apply the Akavia-Moran topology-hiding broadcast for chain-graphs (paths). To prevent topology information revealed by the random-walk, we design multiple random-walks that, together, are locally identical to receiving at each round a message from each neighbors and sending back processed messages in a randomly permuted order.

Adi Akavia, Rio LaVigne, Tal Moran

A New Approach to Round-Optimal Secure Multiparty Computation

Abstract

We present a new approach towards constructing round-optimal secure multiparty computation (MPC) protocols against malicious adversaries without trusted setup assumptions. Our approach builds on ideas previously developed in the context of covert multiparty computation [Chandran et al., FOCS’07] even though we do not seek covert security. Using our new approach, we obtain the following results:

A five round MPC protocol based on the Decisional Diffie-Hellman (DDH) assumption.
A four round MPC protocol based on one-way permutations and sub-exponentially secure DDH. This result is optimal in the number of rounds.

Previously, no four-round MPC protocol for general functions was known and five-round protocols were only known based on indistinguishability obfuscation (and some additional assumptions) [Garg et al., EUROCRYPT’16].

Prabhanjan Ananth, Arka Rai Choudhuri, Abhishek Jain

Award Papers

Frontmatter

Watermarking Cryptographic Functionalities from Standard Lattice Assumptions

Abstract

A software watermarking scheme allows one to embed a “mark” into a program without significantly altering the behavior of the program. Moreover, it should be difficult to remove the watermark without destroying the functionality of the program. Recently, Cohen et al. (STOC 2016) and Boneh et al. (PKC 2017) showed how to watermark cryptographic functions such as PRFs using indistinguishability obfuscation. Notably, in their constructions, the watermark remains intact even against arbitrary removal strategies. A natural question is whether we can build watermarking schemes from standard assumptions that achieve this strong mark-unremovability property.

We give the first construction of a watermarkable family of PRFs that satisfy this strong mark-unremovability property from standard lattice assumptions (namely, the learning with errors (LWE) and the one-dimensional short integer solution (SIS) problems). As part of our construction, we introduce a new cryptographic primitive called a translucent PRF. Next, we give a concrete construction of a translucent PRF family from standard lattice assumptions. Finally, we show that using our new lattice-based translucent PRFs, we obtain the first watermarkable family of PRFs with strong unremovability against arbitrary strategies from standard assumptions.

Sam Kim, David J. Wu

Identity-Based Encryption from the Diffie-Hellman Assumption

Abstract

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.

Nico Döttling, Sanjam Garg

The First Collision for Full SHA-1

Abstract

SHA-1 is a widely used 1995 NIST cryptographic hash function standard that was officially deprecated by NIST in 2011 due to fundamental security weaknesses demonstrated in various analyses and theoretical attacks.

Despite its deprecation, SHA-1 remains widely used in 2017 for document and TLS certificate signatures, and also in many software such as the GIT versioning system for integrity and backup purposes.

A key reason behind the reluctance of many industry players to replace SHA-1 with a safer alternative is the fact that finding an actual collision has seemed to be impractical for the past eleven years due to the high complexity and computational cost of the attack.

In this paper, we demonstrate that SHA-1 collision attacks have finally become practical by providing the first known instance of a collision. Furthermore, the prefix of the colliding messages was carefully chosen so that they allow an attacker to forge two distinct PDF documents with the same SHA-1 hash that display different arbitrarily-chosen visual contents.

We were able to find this collision by combining many special cryptanalytic techniques in complex ways and improving upon previous work. In total the computational effort spent is equivalent to \(2^{63.1}\) calls to SHA-1’s compression function, and took approximately 6 500 CPU years and 100 GPU years. While the computational power spent on this collision is larger than other public cryptanalytic computations, it is still more than 100 000 times faster than a brute force search.

Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov

Obfuscation I

Frontmatter

Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs

Abstract

Two recent works [Lin, EUROCRYPT 2016, Lin and Vaikuntanathan, FOCS 2016] showed how to construct Indistinguishability Obfuscation (IO) from constant degree multilinear maps. However, the concrete degrees of multilinear maps used in their constructions exceed 30. In this work, we reduce the degree of multilinear maps needed to 5, by giving a new construction of IO from asymmetric L-linear maps and a pseudo-random generator (PRG) with output locality L and polynomial stretch. When plugging in a candidate PRG with locality-5 (e.g., [Goldreich, ECCC 2010, Mossel, Shpilka, and Trevisan, FOCS 2013, O’Donnald and Wither, CCC 2014]), we obtain a construction of IO from 5-linear maps.

Our construction improves the state-of-the-art at two other fronts: First, it relies on “classical” multilinear maps, instead of their powerful generalization of graded encodings. Second, it comes with a security reduction to (i) the SXDH assumption on algebraic multilinear maps [Boneh and Silverberg, Contemporary Mathematics, Rothblum, TCC 2013], (ii) the security of PRG, and (iii) sub-exponential LWE, all with sub-exponential hardness. The SXDH assumption is weaker and/or simpler than assumptions on multilinear maps underlying previous IO constructions. When noisy multilinear maps [Garg et al., EUROCRYPT 2013] are used instead, security is based on a family of more complex assumptions that hold in the generic model.

Huijia Lin

Indistinguishability Obfuscation from Trilinear Maps and Block-Wise Local PRGs

Abstract

We consider the question of finding the lowest degree L for which L-linear maps suffice to obtain IO. The current state of the art (Lin, EUROCRYPT’16, CRYPTO ’17; Lin and Vaikunthanathan, FOCS’16; Ananth and Sahai, EUROCRYPT ’17) is that L-linear maps (under suitable security assumptions) suffice for IO, assuming the existence of pseudo-random generators (PRGs) with output locality L. However, these works cannot answer the question of whether \(L < 5\) suffices, as no polynomial-stretch PRG with locality lower than 5 exists.

In this work, we present a new approach that relies on the existence of PRGs with block-wise locality L, i.e., every output bit depends on at most L (disjoint) input blocks, each consisting of up to \(\log \lambda \) input bits. We show that the existence of PRGs with block-wise locality is plausible for any \(L \ge 3\), and also provide:

A construction of a general-purpose indistinguishability obfuscator from L-linear maps and a subexponentially-secure PRG with block-wise locality L and polynomial stretch.
A construction of general-purpose functional encryption from L-linear maps and any slightly super-polynomially secure PRG with block-wise locality L and polynomial stretch.

All our constructions are based on the SXDH assumption on L-linear maps and subexponential Learning With Errors (LWE) assumption, and follow by instantiating our new generic bootstrapping theorems with Lin’s recently proposed FE scheme (CRYPTO ’17). Inherited from Lin’s work, our security proof requires algebraic multilinear maps (Boneh and Silverberg, Contemporary Mathematics), whereas security when using noisy multilinear maps is based on a family of more complex assumptions that hold in the generic model.

Our candidate PRGs with block-wise locality are based on Goldreich’s local functions, and we show that the security of instantiations with block-wise locality \(L \ge 3\) is backed by similar validation as constructions with (conventional) locality 5. We further complement this with hardness amplification techniques that further weaken the pseudorandomness requirements.

Huijia Lin, Stefano Tessaro

Lower Bounds on Obfuscation from All-or-Nothing Encryption Primitives

Abstract

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.

Sanjam Garg, Mohammad Mahmoody, Ameer Mohammed

Structure vs. Hardness Through the Obfuscation Lens

Abstract

Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardness of these problems in question. In particular, this structure often puts them in low complexity classes such as \({\textsf {NP}} \cap {\textsf {coNP}}\) or statistical zero-knowledge (SZK).

Is this structure really necessary? For some cryptographic primitives, such as one-way permutations and homomorphic encryption, we know that the answer is yes—they imply hard problems in \({\textsf {NP}} \cap {\textsf {coNP}}\) and \({\textsf {SZK}}\), respectively. In contrast, one-way functions do not imply such hard problems, at least not by fully black-box reductions. Yet, for many basic primitives such as public-key encryption, oblivious transfer, and functional encryption, we do not have any answer.

We show that the above primitives, and many others, do not imply hard problems in \({\textsf {NP}} \cap {\textsf {coNP}}\) or \({\textsf {SZK}}\) via fully black-box reductions. In fact, we first show that even the very powerful notion of Indistinguishability Obfuscation (IO) does not imply such hard problems, and then deduce the same for a large class of primitives that can be constructed from IO.

Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan

Conditional Disclosure of Secrets

Frontmatter

Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-Bounds, and Separations

Abstract

In the conditional disclosure of secrets problem (Gertner et al. J. Comput. Syst. Sci. 2000) Alice and Bob, who hold inputs x and y respectively, wish to release a common secret s to Carol (who knows both x and y) if and only if the input (x, y) satisfies some predefined predicate f. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some joint randomness and the goal is to minimize the communication complexity while providing information-theoretic security.

Following Gay et al. (Crypto 2015), we study the communication complexity of CDS protocols and derive the following positive and negative results.

(Closure): A CDS for f can be turned into a CDS for its complement \(\bar{f}\) with only a minor blow-up in complexity. More generally, for a (possibly non-monotone) predicate h, we obtain a CDS for \(h(f_1,\ldots ,f_m)\) whose cost is essentially linear in the formula size of h and polynomial in the CDS complexity of \(f_i\).
(Amplification): It is possible to reduce the privacy and correctness error of a CDS from constant to \(2^{-k}\) with a multiplicative overhead of O(k). Moreover, this overhead can be amortized over k-bit secrets.
(Amortization): Every predicate f over n-bit inputs admits a CDS for multi-bit secrets whose amortized communication complexity per secret bit grows linearly with the input length n for sufficiently long secrets. In contrast, the best known upper-bound for single-bit secrets is exponential in n.
(Lower-bounds): There exists a (non-explicit) predicate f over n-bit inputs for which any perfect (single-bit) CDS requires communication of at least \(\varOmega (n)\). This is an exponential improvement over the previously known \(\varOmega (\log n)\) lower-bound.
(Separations): There exists an (explicit) predicate whose CDS complexity is exponentially smaller than its randomized communication complexity. This matches a lower-bound of Gay et al., and, combined with another result of theirs, yields an exponential separation between the communication complexity of linear CDS and non-linear CDS. This is the first provable gap between the communication complexity of linear CDS (which captures most known protocols) and non-linear CDS.

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan

Conditional Disclosure of Secrets via Non-linear Reconstruction

Abstract

We present new protocols for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate.

For general predicates \(\mathsf {P}: [N] \times [N] \rightarrow \{0,1\}\), we present two protocols that achieve \(o(N^{1/2})\) communication: the first achieves \(O(N^{1/3})\) communication and the second achieves sub-polynomial \(2^{O(\sqrt{\log N \log \log N})} = N^{o(1)}\) communication.
As a corollary, we obtain improved share complexity for forbidden graph access structures. Namely, for every graph on N vertices, there is a secret-sharing scheme for N parties in which each pair of parties can reconstruct the secret if and only if the corresponding vertices in G are connected, and where each party gets a share of size \(2^{O(\sqrt{\log N \log \log N})} = N^{o(1)}\).

Prior to this work, the best protocols for both primitives required communication complexity \(\tilde{O}(N^{1/2})\). Indeed, this is essentially the best that all prior techniques could hope to achieve as they were limited to so-called “linear reconstruction”. This is the first work to break this \(O(N^{1/2})\) “linear reconstruction” barrier in settings related to secret sharing. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval.

We further extend our results to the setting of private simultaneous messages (PSM), and provide applications such as an improved attribute-based encryption (ABE) for quadratic polynomials.

Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Functional Encryption

Frontmatter

Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks

Generic Transformations of Predicate Encodings: Constructions and Applications

Practical Functional Encryption for Quadratic Functions with Applications to Predicate Encryption

Foundations I

Frontmatter

Memory-Tight Reductions

Be Adaptive, Avoid Overcommitting

Two-Party Computation

Frontmatter

The TinyTable Protocol for 2-Party Secure Computation, or: Gate-Scrambling Revisited

Privacy-Free Garbled Circuits for Formulas: Size Zero and Information-Theoretic

Secure Arithmetic Computation with Constant Computational Overhead

Encryption Switching Protocols Revisited: Switching Modulo p

Bitcoin

Frontmatter

The Bitcoin Backbone Protocol with Chains of Variable Difficulty

Bitcoin as a Transaction Ledger: A Composable Treatment

Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol

Multiparty Computation

Frontmatter

Robust Non-interactive Multiparty Computation Against Constant-Size Collusion

The Price of Low Communication in Secure Multi-party Computation

Topology-Hiding Computation on All Graphs

A New Approach to Round-Optimal Secure Multiparty Computation

Award Papers

Frontmatter

Watermarking Cryptographic Functionalities from Standard Lattice Assumptions

Identity-Based Encryption from the Diffie-Hellman Assumption

The First Collision for Full SHA-1

Obfuscation I

Frontmatter

Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs

Indistinguishability Obfuscation from Trilinear Maps and Block-Wise Local PRGs

Lower Bounds on Obfuscation from All-or-Nothing Encryption Primitives

Structure vs. Hardness Through the Obfuscation Lens

Conditional Disclosure of Secrets

Frontmatter

Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-Bounds, and Separations

Conditional Disclosure of Secrets via Non-linear Reconstruction

Backmatter

Premium Partner