Author name cluster

Craig Gentry

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

1 author row

FOCS Conference 2015 Conference Paper

Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption

Craig Gentry
Allison Bishop Lewko
Amit Sahai
Brent Waters

We revisit the question of constructing secure general-purpose indistinguishability obfuscation, with a security reduction based on explicit computational assumptions over multilinear maps. Previous to our work, such reductions were only known to exist based on meta-assumptions and/or ad-hoc assumptions: In the original constructive work of Garg et al. (FOCS 2013), the underlying explicit computational assumption encapsulated an exponential family of assumptions for each pair of circuits to be obfuscated. In the more recent work of Pass et al. (Crypto 2014), the underlying assumption is a meta-assumption that also encapsulates an exponential family of assumptions, and this meta-assumption is invoked in a manner that captures the specific pair of circuits to be obfuscated. The assumptions underlying both these works substantially capture (either explicitly or implicitly) the actual structure of the obfuscation mechanism itself. In our work, we provide the first construction of general-purpose indistinguishability obfuscation proven secure via a reduction to a natural computational assumption over multilinear maps, namely, the Multilinear Subgroup Elimination Assumption. This assumption does not depend on the circuits to be obfuscated (except for its size), and does not correspond to the underlying structure of our obfuscator. The technical heart of our paper is our reduction, which gives a new way to argue about the security of indistinguishability obfuscation.

Details

FOCS Conference 2014 Conference Paper

Outsourcing Private RAM Computation

Craig Gentry
Shai Halevi
Mariana Raykova 0001
Daniel Wichs

We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client's work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server's work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of reusable garbled RAM programs, addressing an open question of Lu and Ostrovsky (Eurocrypt 2013). We also construct schemes for an augmented variant of the above scenario, where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database. Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required type of reusable garbled circuits from indistinguishability obfuscation or from functional encryption for circuits as a black-box. For the more complex setting with a persistent database, we can instantiate the required type of reusable garbled circuits using stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time pre-processing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether. We show several simple extensions of our results and techniques to achieve: efficiency proportional to the input-specific RAM run-time, verifiability of outsourced RAM computation, functional encryption for RAMs, and a candidate obfuscation for RAMs.

Details

FOCS Conference 2013 Conference Paper

Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits

Sanjam Garg
Craig Gentry
Shai Halevi
Mariana Raykova 0001
Amit Sahai
Brent Waters

In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits C 0 and C 1 of similar size, the obfuscations of C 0 and C 1 should be computationally indistinguishable. In functional encryption, cipher texts encrypt inputs x and keys are issued for circuits C. Using the key SK C to decrypt a cipher text CT x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually. We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps: - (1) We describe a candidate construction for indistinguishability obfuscation for NC 1 circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles. (2) We show how to use indistinguishability obfuscation for NC 1 together with Fully Homomorphic Encryption (with decryption in NC 1 ) to achieve indistinguishability obfuscation for all circuits. (3) Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct cipher texts, which enables several other applications.

Details

STOC Conference 2013 Conference Paper

Witness encryption and its applications

Sanjam Garg
Craig Gentry
Amit Sahai
Brent Waters

We put forth the concept of witness encryption . A witness encryption scheme is defined for an NP language L (with corresponding witness relation R ). In such a scheme, a user can encrypt a message M to a particular problem instance x to produce a ciphertext. A recipient of a ciphertext is able to decrypt the message if x is in the language and the recipient knows a witness w where R(x,w) holds. However, if x is not in the language, then no polynomial-time attacker can distinguish between encryptions of any two equal length messages. We emphasize that the encrypter himself may have no idea whether $x$ is actually in the language. Our contributions in this paper are threefold. First, we introduce and formally define witness encryption. Second, we show how to build several cryptographic primitives from witness encryption. Finally, we give a candidate construction based on the NP-complete Exact Cover problem and Garg, Gentry, and Halevi's recent construction of "approximate" multilinear maps. Our method for witness encryption also yields the first candidate construction for an open problem posed by Rudich in 1989: constructing computational secret sharing schemes for an NP-complete access structure.

Details

FOCS Conference 2011 Conference Paper

Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits

Craig Gentry
Shai Halevi

We describe a new approach for constructing fully homomorphic encryption (FHE) schemes. Previous FHE schemes all use the same blueprint from [Gentry 2009]: First construct a somewhat homomorphic encryption (SWHE) scheme, next "squash" the decryption circuit until it is simple enough to be handled within the homomorphic capacity of the SWHE scheme, and finally "bootstrap" to get a FHE scheme. In all existing schemes, the squashing technique induces an additional assumption: that the sparse subset sum problem (SSSP) is hard. Our new approach constructs FHE as a hybrid of a SWHE and a multiplicatively homomorphic encryption (MHE) scheme, such as Elgamal. Our construction eliminates the need for the squashing step, and thereby also removes the need to assume the SSSP is hard. We describe a few concrete instantiations of the new method, including a "simple" FHE scheme where we replace SSSP with Decision Diffle-Hellman, an optimization of the simple scheme that let us "compress" the FHE ciphertext into a single Elgamal ciphertext(J), and a scheme whose security can be (quantumly) reduced to the approximate ideal-SIVP. We stress that the new approach still relies on bootstrapping, but it shows how to bootstrap without having to "squash" the decryption circuit. The main technique is to express the decryption function of SWHE schemes as a depth-3 Q2 (Σ Π Σ) arithmetic circuit of a particular form. When evaluating this circuit homomorphically (as needed for bootstrapping), we temporarily switch to a MHE scheme, such as Elgamal, to handle the Π part. Due to the special form of the circuit, the switch to the MHE scheme can be done without having to evaluate anything homomorphically. We then translate the result back to the SWHE scheme by homomorphically evaluating the decryption function of the MHE scheme. Using our method, the SWHE scheme only needs to be capable of evaluating the MHE scheme's decryption function, not its own decryption function. We thereby avoid the circularity that necessitated squashing in the original blueprint.

Details

STOC Conference 2011 Conference Paper

Separating succinct non-interactive arguments from all falsifiable assumptions

Craig Gentry
Daniel Wichs

An argument system for NP is succinct, if its communication complexity is polylogarithmic the instance and witness sizes. The seminal works of Kilian '92 and Micali '94 show that such arguments can be constructed under standard cryptographic hardness assumptions with four rounds of interaction, and that they be made non-interactive in the random-oracle model. However, we currently do not have any construction of succinct non-interactive arguments (SNARGs) in the standard model with a proof of security under any simple cryptographic assumption. In this work, we give a broad black-box separation result, showing that black-box reductions cannot be used to prove the security of any SNARG construction based on any falsifiable cryptographic assumption. This includes essentially all common assumptions used in cryptography (one-way functions, trapdoor permutations, DDH, RSA, LWE etc.). More generally, we say that an assumption is falsifiable if it can be modeled as an interactive game between an adversary and an efficient challenger that can efficiently decide if the adversary won the game. This is similar, in spirit, to the notion of falsifiability of Naor '03, and captures the fact that we can efficiently check if an adversarial strategy breaks the assumption. Our separation result also extends to designated verifier SNARGs, where the verifier needs a trapdoor associated with the CRS to verify arguments, and slightly succinct SNARGs, whose size is only required to be sublinear in the statement and witness size.

Details

STOC Conference 2009 Conference Paper

Fully homomorphic encryption using ideal lattices

Craig Gentry

We propose a fully homomorphic encryption scheme -- i.e., a scheme that allows one to evaluate circuits over encrypted data without being able to decrypt. Our solution comes in three steps. First, we provide a general result -- that, to construct an encryption scheme that permits evaluation of arbitrary circuits , it suffices to construct an encryption scheme that can evaluate (slightly augmented versions of) its own decryption circuit ; we call a scheme that can evaluate its (augmented) decryption circuit bootstrappable . Next, we describe a public key encryption scheme using ideal lattices that is almost bootstrappable. Lattice-based cryptosystems typically have decryption algorithms with low circuit complexity, often dominated by an inner product computation that is in NC1. Also, ideal lattices provide both additive and multiplicative homomorphisms (modulo a public-key ideal in a polynomial ring that is represented as a lattice), as needed to evaluate general circuits. Unfortunately, our initial scheme is not quite bootstrappable -- i.e., the depth that the scheme can correctly evaluate can be logarithmic in the lattice dimension, just like the depth of the decryption circuit, but the latter is greater than the former. In the final step, we show how to modify the scheme to reduce the depth of the decryption circuit, and thereby obtain a bootstrappable encryption scheme, without reducing the depth that the scheme can evaluate. Abstractly, we accomplish this by enabling the encrypter to start the decryption process, leaving less work for the decrypter, much like the server leaves less work for the decrypter in a server-aided cryptosystem.

Details

STOC Conference 2008 Conference Paper

Trapdoors for hard lattices and new cryptographic constructions

Craig Gentry
Chris Peikert
Vinod Vaikuntanathan

We show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). Our contributions include a new notion of trapdoor function with preimage sampling , simple and efficient "hash-and-sign" digital signature schemes, and identity-based encryption. A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a discrete Gaussian probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.

Details

FOCS Conference 2007 Conference Paper

Space-Efficient Identity Based Encryption Without Pairings

Dan Boneh
Craig Gentry
Michael Hamburg

Identity Based Encryption (IBE) systems are often constructed using bilinear maps (a. k. a. pairings) on elliptic curves. One exception is an elegant system due to Cocks which builds an IBE based on the quadratic residuosity problem modulo an RSA composite N. The Cocks system, however, produces long ciphertexts. Since the introduction of the Cocks system in 2001 it has been an open problem to construct a space efficient IBE system without pairings. In this paper we present an IBE system in which ciphertext size is short: an encryption of an f. -bit message consists of a single element in Z/NZ plus lscr + 1 additional bits. Security, as in the Cocks system, relies on the quadratic residuosity problem. The system is based on the theory of ternary quadratic forms and as a result, encryption and decryption are slower than in the Cocks system.

Details

FOCS Conference 2006 Conference Paper

Explicit Exclusive Set Systems with Applications to Broadcast Encryption

Craig Gentry
Zulfikar Ramzan
David P. Woodruff

A family of subsets C of [n] = def {1, .. ., n} is (r, t)-exclusive if for every S sub [n] of size at least n - r, there exist S 1, .. ., S t isin C with S = S 1 cupS 2 cup. .. cupS t. These families, also known as complement-cover families, have cryptographic applications, and form the basis of information-theoretic broadcast encryption and multi-certificate revocation. We give the first explicit construction of such families with size poly(r, t)n r t/, essentially matching a basic lower bound. Our techniques are algebraic in nature. When r = O(t), as is natural for many applications, we can improve our bound to poly(r, t)( n r ) 1 t/. Further, when r, t are small, our construction is tight up to a factor of r. We also provide a poly(r, t, log n) algorithm for finding S 1, .. ., S t, which is crucial for efficient use in applications. Previous constructions either had much larger size, were randomized and took super-polynomial time to find S 1, .. ., S t, or did not work for arbitrary n, r, and t. Finally, we improve the known lower bound on the number of sets containing each i isin [n]. Our bound shows that our derived broadcast encryption schemes have essentially optimal total number of keys and keys per user for n users, transmission size t, and revoked set size r

Details