Computing Arbitrary Functions
of Encrypted Data
By Craig Gentry
Suppose that you want to delegate the ability to process your
data, without giving away access to it. We show that this
separation is possible: we describe a “fully homomorphic”
encryption scheme that keeps data private, but that allows a
worker that does not have the secret decryption key to compute any (still encrypted) result of the data, even when the
function of the data is very complex. In short, a third party
can perform complicated processing of data without being
able to see it. Among other things, this helps make cloud
computing compatible with privacy.
Is it possible to delegate processing of your data without giving away access to it?
This question, which tests the tension between convenience and privacy, has always been important, but seems
especially so now that we are headed toward widespread use
of cloud computing. To put everything online “in the cloud,”
unencrypted, is to risk an Orwellian future. For certain types
of data, such as medical records, storing them off-site unencrypted may be illegal. On the other hand, encrypting one’s
data seems to nullify the benefits of cloud computing. Unless
I give the cloud my secret decryption key (sacrificing my privacy), what can I expect the cloud to do with my encrypted
data except send it back to me, so that I can decrypt it and
process it myself?
Fortunately, this is a false dilemma, or at least convenience and privacy can be reconciled to a large extent.
For data that is encrypted with an “ordinary” encryption
scheme, it is virtually impossible for someone without the
secret decryption key (such as the cloud) to manipulate the
underlying data in any useful way. However, some encryption schemes are homomorphic or malleable. They let anyone
manipulate (in a meaningful way) what is encrypted, even
without knowing the secret key!
In this paper, we describe the first fully homomorphic
encryption (FHE) scheme, where “fully” means that there
are no limitations on what manipulations can be performed. Given ciphertexts c1, …, ct that encrypt m1, …, mt with
our scheme under some key, and given any efficiently computable function f, anyone can efficiently compute a ciphertext (or set of ciphertexts) that encrypts f (m1, …, mt) under
that key. In short, this permits general computations on
encrypted data. No information about m1, …, mt or the value
of f (m1, …, mt) is leaked.
This means that cloud computing is consistent with
privacy. If I want the cloud to compute for me some func-
tion f of my (encrypted) data m1, …, mt—for example,
this function could be “all files containing ‘CACM’ or
‘Communications’ within three words of ‘ACM’”—I send
a description of f to the cloud, which uses the scheme’s
malleability to compute an encryption of f (m1, …, mt ), which
I decrypt. The cloud never sees any unencrypted data.
If I want, I can even use the scheme to encrypt a descrip-
tion of f, so that the cloud does not even see what I am
2. homomoRPhIC enCRYPtIon
2. 1. Alice’s jewelry store
At first, the notion of processing data without having
access to it may seem paradoxical, even logically impos-
sible. To convince you that there is no fallacy, and to give
you some intuition about the solution, let us consider an
analogous problem in (a fictional version of) the “physical
Alice owns a jewelry store. She has raw precious mate-
rials—gold, diamonds, silver, etc.—that she wants her
workers to assemble into intricately designed rings and
This paper draws from the STOC 2009 paper “Fully
Homomorphic Encryption Using Ideal Lattices,” my
thesis, and a recent manuscript co-authored with van
Dijk, Halevi, and Vaikuntanathan.