## CryptoDB

### Craig Gentry

#### Affiliation: IBM Watson

#### Publications

**Year**

**Venue**

**Title**

2019

TCC

Compressible FHE with Applications to PIR
Abstract

Homomorphic encryption (HE) is often viewed as impractical, both in communication and computation. Here we provide an additively homomorphic encryption scheme based on (ring) LWE with nearly optimal rate ($$1-\epsilon $$ for any $$\epsilon >0$$). Moreover, we describe how to compress many Gentry-Sahai-Waters (GSW) ciphertexts (e.g., ciphertexts that may have come from a homomorphic evaluation) into (fewer) high-rate ciphertexts.Using our high-rate HE scheme, we are able for the first time to describe a single-server private information retrieval (PIR) scheme with sufficiently low computational overhead so as to be practical for large databases. Single-server PIR inherently requires the server to perform at least one bit operation per database bit, and we describe a rate-(4/9) scheme with computation which is not so much worse than this inherent lower bound. In fact it is probably less than whole-database AES encryption – specifically about 2.3 mod-q multiplication per database byte, where q is about 50 to 60 bits. Asymptotically, the computational overhead of our PIR scheme is $$\tilde{O}(\log \log \mathsf {\lambda }+ \log \log \log N)$$, where $$\mathsf {\lambda }$$ is the security parameter and N is the number of database files, which are assumed to be sufficiently large.

2019

ASIACRYPT

Homomorphic Encryption for Finite Automata
Abstract

We describe a somewhat homomorphic GSW-like encryption scheme, natively encrypting matrices rather than just single elements. This scheme offers much better performance than existing homomorphic encryption schemes for evaluating encrypted (nondeterministic) finite automata (NFAs). Differently from GSW, we do not know how to reduce the security of this scheme from LWE, instead we reduce it from a stronger assumption, that can be thought of as an inhomogeneous variant of the NTRU assumption. This assumption (that we term iNTRU) may be useful and interesting in its own right, and we examine a few of its properties. We also examine methods to encode regular expressions as NFAs, and in particular explore a new optimization problem, motivated by our application to encrypted NFA evaluation. In this problem, we seek to minimize the number of states in an NFA for a given expression, subject to the constraint on the ambiguity of the NFA.

2018

PKC

A Unified Framework for Trapdoor-Permutation-Based Sequential Aggregate Signatures
Abstract

We give a framework for trapdoor-permutation-based sequential aggregate signatures (SAS) that unifies and simplifies prior work and leads to new results. The framework is based on ideal ciphers over large domains, which have recently been shown to be realizable in the random oracle model. The basic idea is to replace the random oracle in the full-domain-hash signature scheme with an ideal cipher. Each signer in sequence applies the ideal cipher, keyed by the message, to the output of the previous signer, and then inverts the trapdoor permutation on the result. We obtain different variants of the scheme by varying additional keying material in the ideal cipher and making different assumptions on the trapdoor permutation. In particular, we obtain the first scheme with lazy verification and signature size independent of the number of signers that does not rely on bilinear pairings.Since existing proofs that ideal ciphers over large domains can be realized in the random oracle model are lossy, our schemes do not currently permit practical instantiation parameters at a reasonable security level, and thus we view our contribution as mainly conceptual. However, we are optimistic tighter proofs will be found, at least in our specific application.

2015

JOFC

2014

CRYPTO

2014

EUROCRYPT

2013

CRYPTO

2010

EPRINT

A Simple BGN-type Cryptosystem from LWE
Abstract

We construct a simple public-key encryption scheme that supports polynomially many additions and one multiplication, similar to the cryptosystem of Boneh, Goh, and Nissim (BGN). Security is based on the hardness of the learning with errors (LWE) problem, which is known to be as hard as certain worst-case lattice problems.
Some features of our cryptosystem include support for large message space, an easy way of achieving formula-privacy, a better message-to-ciphertext expansion ratio than BGN, and an easy way of multiplying two encrypted polynomials. Also, the scheme can be made identity-based and leakage-resilient (at the cost of a higher message-to-ciphertext expansion ratio).

2010

EPRINT

i-Hop Homomorphic Encryption and Rerandomizable Yao Circuits
Abstract

Homomorphic encryption (HE) schemes enable computing functions on encrypted data, by means of a public $\Eval$ procedure that can be applied to ciphertexts. But the evaluated ciphertexts so generated may differ from freshly encrypted ones. This brings up the question of whether one can keep computing on evaluated ciphertexts. An \emph{$i$-hop} homomorphic encryption scheme is one where $\Eval$ can be called on its own output up to $i$~times, while still being able to decrypt the result. A \emph{multi-hop} homomorphic encryption is a scheme which is $i$-hop for all~$i$. In this work we study $i$-hop and multi-hop schemes in conjunction with the properties of function-privacy (i.e., $\Eval$'s output hides the function) and compactness (i.e., the output of $\Eval$ is short). We provide formal definitions and describe several constructions.
First, we observe that "bootstrapping" techniques can be used to convert any (1-hop) homomorphic encryption scheme into an $i$-hop scheme for any~$i$, and the result inherits the function-privacy and/or compactness of the underlying scheme. However, if the underlying scheme is not compact (such as schemes derived from Yao circuits) then the complexity of the resulting $i$-hop scheme can be as high as $k^{O(i)}$.
We then describe a specific DDH-based multi-hop homomorphic encryption scheme that does not suffer from this exponential blowup. Although not compact, this scheme has complexity linear in the size of the composed function, independently of the number of hops. The main technical ingredient in this solution is a \emph{re-randomizable} variant of the Yao circuits. Namely, given a garbled circuit, anyone can re-garble it in such a way that even the party that generated the original garbled circuit cannot recognize it. This construction may be of independent interest.

2009

EPRINT

Attacking Cryptographic Schemes Based on "Perturbation Polynomials"
Abstract

We show attacks on several cryptographic schemes that have recently been proposed for achieving various security goals in sensor networks. Roughly speaking, these schemes all use "perturbation polynomials" to add "noise" to polynomial-based systems that offer information-theoretic security, in an attempt to increase the resilience threshold while maintaining efficiency. We show that the heuristic security arguments given for these modified schemes do not hold, and that they can be completely broken once we allow even a slight extension of the parameters beyond those achieved by the underlying information-theoretic schemes.
Our attacks apply to the key predistribution scheme of Zhang et al. (MobiHoc~2007), the access-control schemes of Subramanian et al. (PerCom~2007), and the authentication schemes of Zhang et~al. (INFOCOM~2008).

2008

EPRINT

Adaptive Security in Broadcast Encryption Systems
Abstract

We present new techniques for achieving adaptive security
in broadcast encryption systems. Previous work on fully-collusion
resistant broadcast encryption with short ciphertexts was limited
to only considering static security.
First, we present a new definition of security that we call
semi-static security and show a generic ``two-key"
transformation from semi-statically secure systems to adaptively
secure ones that have comparable-sized ciphertexts. Using bilinear
maps, we then construct broadcast encryption systems that are
semi-statically secure in the standard model and have constant
size ciphertexts. Our semi-static constructions work when the
number of indices or identifiers in the system is polynomial in
the security parameter.
For identity-based broadcast encryption, where the number of
potential indices or identifiers may be exponential, we present
the first adaptively secure system with sublinear ciphertexts. We
prove security in the standard model.

2007

EPRINT

Space-Efficient Identity Based Encryption Without Pairings
Abstract

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 L-bit message
consists of a single element in Z_N plus L+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.

2007

EPRINT

Trapdoors for Hard Lattices and New Cryptographic Constructions
Abstract

We show how to construct a variety of ``trapdoor'' cryptographic tools
assuming the worst-case hardness of standard lattice problems (such as
approximating the shortest nonzero vector to within small factors).
The applications include trapdoor functions with \emph{preimage
sampling}, simple and efficient ``hash-and-sign'' digital signature
schemes, universally composable oblivious transfer, 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 Gaussian-like probability distribution whose standard
deviation is essentially the length of the longest vector in the
basis. In particular, the crucial security property is that the
output distribution of the algorithm is oblivious to the particular
geometry of the given basis.

2007

EPRINT

Ordered Multisignatures and Identity-Based Sequential Aggregate Signatures, with Applications to Secure Routing
Abstract

We construct two new multiparty digital signature schemes that allow multiple signers to sequentially produce a compact, fixed-length signature. First, we introduce a new primitive that we call \emph{ordered multisignatures} (OMS), which allows signers to attest to a common message as well as the order in which they signed. Our OMS construction substantially improves computational efficiency and scalability over any existing scheme with suitable functionality. Second, we design a new identity-based sequential aggregate signature scheme, where signers can attest to different messages and signature verification does not require knowledge of traditional public keys. The latter property permits savings on bandwidth and storage as compared to public-key solutions. In contrast to the only prior scheme to provide this functionality, ours offers improved security that does not rely on synchronized clocks or a trusted first signer. We provide formal security definitions and support the proposed schemes with security proofs under appropriate computational assumptions. We focus on potential applications of our schemes to secure network routing, but we believe they will find many other applications as well.

2005

ASIACRYPT

2005

EPRINT

Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys
Abstract

We describe two new public key broadcast encryption systems for
stateless receivers. Both systems are fully secure against any number
of colluders. In our first construction both ciphertexts and private
keys are of constant size (only two group elements), for any
subset of receivers. The public key size in this system is
linear in the total number of receivers. Our second system is a
generalization of the first that provides a tradeoff between
ciphertext size and public key size. For example, we achieve a
collusion resistant broadcast system for n users where both
ciphertexts and public keys are of size O(sqrt(n)) for any subset
of receivers. We discuss several applications of these systems.

2003

EPRINT

Certificate-Based Encryption and the Certificate Revocation Problem
Abstract

We introduce the notion of certificate-based encryption. In this model, a certificate -- or, more generally, a signature -- acts not only as a certificate but also as a decryption key. To decrypt a message, a keyholder needs both its secret key and an up-to-date certificate from its CA (or a signature from an authorizer). Certificate-based encryption combines the best aspects of identity-based encryption (implicit certification) and public key encryption (no escrow). We demonstrate how certificate-based encryption can be used to construct an efficient PKI requiring less infrastructure than previous proposals, including Micali's Novomodo, Naor-Nissim and Aiello-Lodha-Ostrovsky.

2002

EPRINT

Hierarchical ID-Based Cryptography
Abstract

We present hierarchical identity-based encryption schemes and signature schemes that have total collusion resistance on an arbitrary number of levels and that have chosen ciphertext security in the random oracle model assuming the difficulty of the Bilinear Diffie-Hellman problem.

2002

EPRINT

Aggregate and Verifiably Encrypted Signatures from Bilinear Maps
Abstract

An aggregate signature scheme is a digital signature that supports
aggregation: Given $n$ signatures on $n$ distinct messages from
$n$ distinct users, it is possible to aggregate all these
signatures into a single short signature. This single signature
(and the $n$ original messages) will convince the verifier that
the $n$ users did indeed sign the $n$ original messages (i.e.,
user $i$ signed message $M_i$ for $i=1,\ldots,n$). In this paper
we introduce the concept of an aggregate signature scheme, present
security models for such signatures, and give several applications
for aggregate signatures. We construct an efficient aggregate
signature from a recent short signature scheme based on bilinear
maps due to Boneh, Lynn, and Shacham. Aggregate signatures are
useful for reducing the size of certificate chains (by aggregating
all signatures in the chain) and for reducing message size in
secure routing protocols such as SBGP. We also show that
aggregate signatures give rise to verifiably encrypted signatures.
Such signatures enable the verifier to test that a given
ciphertext $C$ is the encryption of a signature on a given message
$M$. Verifiably encrypted signatures are used in contract-signing
protocols. Finally, we show that similar ideas can be used to
extend the short signature scheme to give simple ring signatures.

#### Program Committees

- Crypto 2014
- Asiacrypt 2011
- Crypto 2011
- PKC 2010
- Eurocrypt 2009
- PKC 2008
- Crypto 2008
- Asiacrypt 2007
- Crypto 2005
- CHES 2003
- CHES 2002

#### Coauthors

- Shweta Agrawal (1)
- Martin R. Albrecht (1)
- Allison Bishop (3)
- Alexandra Boldyreva (1)
- Dan Boneh (7)
- Zvika Brakerski (2)
- Yilei Chen (1)
- Jean-Sébastien Coron (2)
- Farid F. Elwailly (1)
- Sanjam Garg (6)
- Nicholas Genise (1)
- Rosario Gennaro (2)
- Sergey Gorbunov (3)
- Jens Groth (1)
- Shai Halevi (32)
- Mike Hamburg (1)
- Yuval Ishai (1)
- Jakob Jonsson (1)
- Charanjit S. Jutla (1)
- Jonathan Katz (1)
- Tancrède Lepoint (3)
- Baiyu Li (1)
- Steve Lu (1)
- Ben Lynn (2)
- Philip D. MacKenzie (1)
- Hemanta K. Maji (2)
- Daniele Micciancio (1)
- Eric Miles (2)
- David Molnar (1)
- Valeria Nikolaenko (2)
- Adam O'Neill (1)
- Rafail Ostrovsky (1)
- Adam O’Neill (1)
- Bryan Parno (2)
- Chris Peikert (2)
- Zulfikar Ramzan (5)
- Mariana Raykova (8)
- Leonid Reyzin (1)
- Amit Sahai (8)
- Gil Segev (2)
- Hovav Shacham (2)
- Alice Silverberg (2)
- Nigel P. Smart (3)
- Adam Smith (1)
- Jacques Stern (1)
- Michael Szydlo (2)
- Mehdi Tibouchi (3)
- Vinod Vaikuntanathan (8)
- Marten van Dijk (1)
- Dhinakaran Vinayagamurthy (2)
- Brent Waters (9)
- Daniel Wichs (4)
- Dae Hyun Yum (1)
- Mark Zhandry (2)