Home/Magazine Archive/March 2010 (Vol. 53, No. 3)/Computing Arbitrary Functions of Encrypted Data/Full Text

Research highlights
## Computing Arbitrary Functions of Encrypted Data

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 *c*_{1}, ..., *c*_{t} that encrypt *m*_{1}, ..., *m*_{t} 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*(*m*_{1}, ..., *m*_{t}) under that key. In short, this permits general computations on encrypted data. No information about *m*_{1}, ..., *m*_{t} or the value of *f*(*m*_{1}, ..., *m*_{t}) is leaked.

This means that cloud computing is consistent with privacy. If I want the cloud to compute for me some function *f* of my (encrypted) data *m*_{1}, ..., *m*_{t}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*(*m*_{1}, ..., *m*_{t}), which I decrypt. The cloud never sees any unencrypted data. If I want, I can even use the scheme to encrypt a description of *f*, so that the cloud does not even see what I am searching for.

Rivest, Adleman, and Dertouzos^{5} suggested that fully homomorphic encryption may be possible in 1978, shortly after the invention of the RSA cryptosystem,^{6} but were unable to find a secure scheme. As an application, they described our private cloud computing scenario above, though of course they used different terminology. There are many other applications. Homomorphic encryption is useful whenever it is acceptable if a response (e.g., to a search engine query) is encrypted.

Below, we begin by describing homomorphic encryption in more detail. Then, we describe a concrete scheme due to van Dijk, Gentry, Halevi, and Vaikuntanathan,^{9} which uses only simple integer operations, and is a conceptually simpler version of the first scheme by Gentry,^{2, 3} which uses lattices. Toward the end, we discuss the scheme's (rather slow) performance. Throughout, we try to make the ideas more tangible by constantly returning to a physical analogy: a jewelry store owner, Alice, who wants her workers to *process* raw precious materials into intricately designed rings and necklaces, but who is afraid to give her workers complete *access* to the materials for fear of theft.

**2.1. Alice's jewelry store**

At first, the notion of processing data without having access to it may seem paradoxical, even logically impossible. 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 world."

Alice owns a jewelry store. She has raw precious materialsgold, diamonds, silver, etc.that she wants her workers to assemble into intricately designed rings and necklaces. But she distrusts her workers and assumes that they will steal her jewels if given the opportunity. In other words, she wants her workers to *process* the materials into finished pieces, without giving them *access* to the materials. What does she do?

Here is her plan. She uses a transparent impenetrable glovebox, secured by a lock for which only she has the key. She puts the raw precious materials inside the box, locks it, and gives it to a worker. Using the gloves, the worker assembles the ring or necklace inside the box. Since the box is impenetrable, the worker cannot get to the precious materials, and figures he might as well return the box to Alice, with the finished piece inside. Alice unlocks the box with her key and extracts the ring or necklace. In short, the worker processes the raw materials into a finished piece, without having true access to the materials.

The locked impenetrable box, with raw precious materials inside, represents an encryption of the initial data *m*_{1}, ..., *m*_{t}, which can be accessed only with the secret decryption key. The gloves represent the homomorphism or malleability of the encryption scheme, which allows the raw data to be manipulated while it is inside the "encryption box." The completed ring or necklace inside the box represents the encryption of *f*(*m*_{1}, ..., *m*_{t}), the desired function of the initial data. Note that "lack of access" is represented by lack of physical access, as opposed to lack of visual access, to the jewels. (For an analogy that uses lack of visual access, consider a photograph developer's darkroom.)

Of course, Alice's jewelry store is only an analogy. It does not represent some aspects of homomorphic encryption well, and taking it too literally may be more confusing than helpful. We discuss some flaws in the analogy at the end of this section, after we describe homomorphic encryption more formally. Despite its flaws, we return to the analogy throughout, since it motivates good questions, and represents some aspects of our solution quite wellmost notably, "bootstrapping," which we discuss in Section 4.

**2.2. Homomorphic encryption: functionality**

An encryption scheme ε has three algorithms: KeyGen_{ε}, Encrypt_{ε}, and Decrypt_{ε}, all of which must be *efficient*that is, run in time poly(λ), polynomial in a security parameter λ that specifies the bit-length of the keys. In a *symmetric*, or *secret key*, encryption scheme, KeyGen_{ε} uses λ to generate a single key that is used in both Encrypt_{ε} and Decrypt_{ε}, first to map a message to a ciphertext, and then to map the ciphertext back to the message. In an *asymmetric*, or *public key*, encryption scheme, KeyGen_{ε} uses λ to generate two keysa public encryption key pk, which may be made available to everyone, and a secret decryption key sk. As a physical analogy for an asymmetric encryption scheme, one can think of Alice's public key as a padlock, which she constructs and distributes, that can be locked without a key. Anyone can put a message inside a box secured by Alice's padlock (encrypt), and mail it via a public channel to Alice, but only Alice has the key needed to unlock it (decrypt).

A homomorphic encryption scheme can be either symmetric or asymmetric, but we will focus on the asymmetric case. It has a fourth algorithm Evaluate_{ε}, which is associated to a set of *permitted functions.* For any function *f* in and any ciphertexts *c*_{1}, ..., *c*_{t} with *c*_{i} ← Encrypt_{ε} (pk, *m*_{i}), the algorithm Evaluate_{ε} (pk, *f, c*_{1}, ..., *c*_{t}) outputs a ciphertext *c* that encrypts *f*(*m*_{1}, ..., *m*_{t})i.e., such that Decrypt_{ε} (sk, *c*) = *f*(*m*_{1}, ..., *m*_{t}). (For convenience, we will assume that *f* has one output. If *f* has *k* outputs, then Evaluate_{ε} outputs *k* ciphertexts that encrypt *f*(*m*_{1}, ..., *m*_{t}) collectively.) As shorthand, we say that ε can *handle* functions in . For a function *f* not in , there is no guarantee that Evaluate_{ε} will output anything meaningful. Typically Evaluate_{ε} is undefined for such a function.

As described thus far, it is trivial to construct an encryption scheme that can handle all functions. Just define Evaluate_{ε} as follows: simply output *c* ← (*f, c*_{1}, ..., *c*_{t}), without "processing" the ciphertexts at all. Modify Decrypt_{ε} slightly: to decrypt *c*, decrypt *c*_{1}, ..., *c*_{t} to obtain *m*_{1}, ..., *m*_{t}, and then apply *f* to these messages.

But this trivial solution obviously does not conform to the spirit of what we are trying to achieveto *delegate* the data processing (while maintaining privacy). The trivial solution is as if, in Alice's jewelry store, the worker simply sends the box (which need not have gloves) back to Alice without doing any work on the raw precious materials, and Alice unlocks the box, extracts the materials, and assembles the ring or necklace herself.

So, how do we formalize what it means to *delegate?* Intuitively, the purpose of delegation is to reduce one's workload. We can formalize this in terms of the running times (i.e., complexity) of the algorithms. Specifically, we require that decrypting *c* (the ciphertext output by Evaluate_{ε}) takes the *same amount of computation* as decrypting *c*_{1} (a ciphertext output by Encrypt_{ε}). Moreover, we require that *c* is the same size as *c*_{1}. We refer to these as the *compact ciphertexts* requirement. Again, the size of *c* and the time needed to decrypt it do not grow with the complexity of *f*; rather, they are *completely independent* of *f* (unless *f* has multiple outputs). Also, of course, the complexity of Decrypt_{ε}, as well as the complexity of KeyGen_{ε} and Encrypt_{ε}, must remain polynomial in λ.

ε is *fully homomorphic* if it can handle all functions, has compact ciphertexts, and Evaluate_{ε} is efficient in a way that we specify below. The trivial solution above certainly is not fully homomorphic, since the size of the ciphertext output by Evaluate_{ε}, as well as the time needed to decrypt it, depend on the function being evaluated. In terms of Alice's jewelry store, our definition of fully homomorphic captures the best-case scenario for Alice: her workers can assemble arbitrarily complicated pieces inside the box, but the work needed to assemble has no bearing on the work Alice needs to do to unlock the box and extract the piece.

We want our fully homomorphic scheme to be efficient for the worker, as well. In particular, we want the complexity of Evaluate_{ε}like the other algorithms of εto depend only polynomially on the security parameter. But clearly its complexity must also depend on the function being evaluated. How do we measure the complexity of *f*? Perhaps the most obvious measure is the running time *T*_{f} of a Turing machine that computes *f*. We use a related measure, the size *S*_{f} of a *boolean circuit* (i.e., the number of AND, OR, and NOT gates) that computes *f*. Any function that can be computed in *T*_{f} steps on a Turing machine can be expressed as a circuit with about *T*_{f} gates. More precisely, *S*_{f} < k · *T*_{f} · log *T*_{f} for some small constant *k*. Overall, we say that Evaluate_{ε} is efficient if there is a polynomial *g* such that, for any function *f* that is represented by a circuit of size *S*_{f}, Evaluate_{ε} (pk, *f, c*_{1}, ..., *c*_{t}) has complexity at most *S*_{f} · *g*(λ).

The circuit representation of *f* is also useful because it breaks the computation of *f* down into simple stepse.g., AND, OR, and NOT gates. Moreover, to evaluate these gates, it is enough to be able to add, subtract, and multiply. (In fact, it is enough if we can add, subtract and multiply *modulo* 2.) In particular, for *x, y* {0, 1}, we have AND(*x, y*) = *xy*, OR(*x, y*) = 1 − (1 − *x*)(1 − *y*) and NOT(*x*) = 1 − *x*. So, to obtain a fully homomorphic encryption scheme, all we need is a scheme that operates on ciphertexts so as to add, subtract, and multiply the underlying messages, indefinitely.

But is the circuit representation of *f*or some arithmetized version of it in terms of addition, subtraction, and multiplicationnecessarily the *most efficient* way to evaluate *f*? In fact, some functions, like binary search, take much longer on a Turing machine or circuit than on a random access machine. On a random access machine, a binary search algorithm on *t* ordered items only needs to "touch" *O*(log *t*) of its inputs.

A moment's thought shows that random-access speed-ups cannot work if the data is encrypted. Unless we know something a priori about the relationship between *f* and *m*_{1}, ..., *m*_{t}, the algorithm Evaluate_{ε}(pk, *f, c*_{1}, ..., *c*_{t}) must touch all of the input ciphertexts, and therefore have complexity at least linear in the number of inputs. To put it another way, if Evaluate_{ε} (for some reason) did not touch the second half of the ciphertexts, this would leak information about the second half of the underlying messagesnamely, their irrelevance in the computation of *f*and this leakage would contradict the security of the encryption scheme. While Evaluate_{ε} must have running time at least linear in *t* as an unavoidable cost of the complete privacy that homomorphic encryption provides, a trade-off is possible. If I am willing to reveale.g., in the cloud computing contextthat the files that I want are contained in a certain 1% of my data, then I may help the cloud reduce its work by a factor of 100.

Another artifact of using a fixed circuit representation of *f* is that the size of the outputi.e., the number of output wires in the circuitmust be fixed in advance. For example, when I request all of my files that contain a combination of keywords, I should also specify how much data I want retrievede.g., 1MB. From my request, the cloud will generate a circuit for a function that outputs the first megabyte of the correct files, where that output is truncated (if too much of my data satisfies my request), or padded with zeros (if too little). A moment's thought shows that this is also unavoidable. There is no way the cloud can avoid truncating or padding unless it knows something a priori about the relationship between the function and my data.

**2.3. Homomorphic encryption: security**

In terms of security, the weakest requirement for an encryption scheme is *one-wayness*: given the public key pk and a ciphertext *c* that encrypts unknown message *m* under pk, it should be "hard" to output *m*. "Hard" means that any algorithm or "adversary" *A* that runs in poly(λ) time has a negligible probability of success over the choices of pk and *m* (i.e., the probability it outputs *m* is less than 1/λ^{k} for any constant *k*).

Nowadays, we typically require an encryption scheme to have a stronger security property, called *semantic security* against chosen-plaintext attacks (CPA)^{4}: given a ciphertext *c* that encrypts either *m*_{0} or *m*_{1}, it is hard for an adversary to decide which, even if it is allowed to choose *m*_{0} and *m*_{1}. Here, "hard" means that if the adversary *A* runs in polynomial time and guesses correctly with probability 1/2 + , then , called *A's advantage*, must be negligible. If this advantage is nonnegligible, then we say (informally) that the adversary *breaks* the semantic security of the encryption scheme.

If an encryption scheme is *deterministic*i.e., if there is only one ciphertext that encrypts a given messagethen it cannot be semantically secure. An attacker can easily tell whether *c* encrypts *m*_{0}, by running *c*_{0} ← Encrypt(pk, *m*_{0}) and seeing if *c* and *c*_{0} are the same. A semantically secure encryption scheme must be *probabilistic*i.e., there must be many ciphertexts that encrypt a given message, and Encrypt_{ε} must choose one randomly according to some distribution.

One can *prove* the (conditional) one-wayness or semantic security of an encryption scheme by *reducing* a hard problem to breaking the encryption scheme. For example, suppose one shows that if there is an efficient algorithm that breaks the encryption scheme, then this algorithm can be used as a subroutine in an efficient algorithm that factors large numbers. Then, under the assumption that factoring is hardi.e., that no poly(λ)-time algorithm can factor λ-bit numbersthe reduction implies that the encryption scheme must be hard to break.

Semantic security of a homomorphic encryption scheme is defined in the same way as for an ordinary encryption scheme, without reference to the Evaluate_{ε} algorithm. If we manage to prove a reductioni.e., that an attacker that breaks ε can be used to solve a hard problem like factoringthen this reduction holds whether or not ε has an Evaluate_{ε} algorithm that works for a large set of functions.

To understand the power of semantic security, let us reconsider our cloud computing application. Sometime after storing her encrypted files in the cloud, Alice wants the cloud to retrieve the files that have a certain combination of keywords. Suppose that in its response, the cloud sends ciphertexts that encrypt the first three files. Can't the cloud just *see* that the first three encrypted files that it is storing for Alice happen to encrypt the same content as the three files that it sends to Alice? Not if the scheme is semantically secure. Even though some of the stored ciphertexts encrypt the same content as the sent ciphertexts, the cloud cannot *see* this, because semantic security guarantees that it is hard to tell whether two ciphertexts encrypt the same content.

Intuitively, it seems like the Evaluate_{ε} algorithm should make ε easier to break, simply because this additional algorithm gives the attacker more power. Or, to put it in terms of the physical analogy, one would think that the easiest way to get inside the glovebox is to cut through the gloves, and that, the more flexible the gloves are, the easier the glovebox is to compromise; this suggests that, the more malleable the encryption scheme is, the easier it is to break. There is some truth to this intuition. Researchers^{1, 8} showed that if ε is a *deterministic* fully homomorphic encryption scheme (or, more broadly, one for which it is easy to tell whether two ciphertexts encrypt the same thing), then ε can be broken in subexponential time, and in only polynomial time (i.e., efficiently) on a quantum computer. So, malleability seems to weaken the security of deterministic schemes. But these results do not apply to semantically secure schemes, such as ours.

**2.4. Some flaws in the physical analogy**

The physical analogy represents some aspects of homomorphic encryption poorly. For example, the physical analogy suggests that messages that are encrypted separately are in different "encryption boxes" and cannot interact. Of course, this interaction is precisely the purpose of homomorphic encryption. To fix the analogy, one may imagine that the gloveboxes have a one-way insertion slot like the mail bins used by the post office. Then, messages can be added to the same encryption box as they arrive. (Even this fix is not entirely satisfactory.)

Another flaw is that the output *f*(*m*_{1}, ..., *m*_{t}) may have significantly fewer bits than *m*_{1}, ..., *m*_{t}, whereas in the analogy (absent significant nuclear activity inside the glovebox) the conservation of mass dictates that the box will have at least as much material inside when the worker is done as when he started. Finally, in Alice's jewelry store, even though a worker cannot extract the materials from a locked glovebox, he can easily tell whether or not a box contains a certain set of materialsi.e., the gloveboxes do not provide "semantic security."

On our way to fully homomorphic encryption, we begin by constructing a *somewhat homomorphic* encryption scheme ε that can handle a limited class of permitted functions. Evaluate_{ε} (pk, *f, c*_{1}, ..., *c*_{t}) does not work for functions *f* that are too complicated. Later, we will show to use ε to obtain fully homomorphic encryption.

**3.1. Meanwhile in Alice's jewelry store**

After figuring out how to use locked gloveboxes to get her workers to process her precious materials into fancy rings and necklaces, Alice puts in an order with Acme Glovebox Company. Unfortunately, the gloveboxes she receives are defective. After a worker uses the gloves for 1 min, the gloves stiffen and become unusable. But some of the fanciest pieces take up to an hour to assemble. Alice sues Acme, but meanwhile she wonders: Is there some way I can use these defective boxes to get the workers to securely assemble even the most complicated pieces?

She notices that the boxes, while defective, do have a property that might be useful. As expected, they have a oneway insertion slot, like post office mail bins. But they are also flexible enough so that it is possible to put one box inside another through the slot. She wonders whether this property might play a role in the solution to her problem, etc.

**3.2. Our somewhat homomorphic scheme**

Our somewhat homomorphic encryption scheme ε, described below, is remarkably simple.^{9} We describe it first as a symmetric encryption scheme. As an example parameter setting, for security parameter λ, set *N* = λ, *P* = λ^{2} and *Q* = λ^{5}.

*An Encryption Scheme:*

- KeyGen
_{ε}(λ): The key is a random*P*-bit odd integer*p*. - Encrypt
_{ε}(*p, m*): To encrypt a bit*m*{0, 1}, set*m'*to be a random*N*-bit number such that*m' = m*mod 2. Output the ciphertext*c*←*m'*+*pq*, where*q*is a random*Q*-bit number. - Decrypt
_{ε}(*p, c*): Output (*c*mod*p*) mod 2, where (*c*mod*p*) is the integer*c'*in (−*p*/2,*p*/2) such that*p*divides*c − c'*.

Ciphertexts from ε are *near-multiples* of *p.* We call (*c* mod *p*) the *noise* associated to the ciphertext *c.* It is the distance to the nearest multiple of *p.* Decryption works because the noise is *m'*, which has the same parity as the message. We call a ciphertext output by Encrypt a *fresh* ciphertext, since it has small (*N*-bit) noise.

How is the scheme homomorphic? By simply adding, subtracting, or multiplying the ciphertexts as integers, we can add, subtract, or multiply (modulo 2) the underlying messages. However, complications arise, because these operations increase the noise associated to resulting ciphertexts. Eventually, the noise become so large that decryption no longer reliably returns the correct result.

*Homomorphic Operations:*

- Add
_{ε}(*c*_{1},*c*_{2}), Sub_{ε}(*c*_{1},*c*_{2}), Mult_{ε}(*c*_{1},*c*_{2}): the output ciphertext*c*is*c*_{1}+*c*_{2},*c*_{1}−*c*_{2}, or*c*_{1}·*c*_{2}. - Evaluate
_{ε}(*f, c*_{1}, ...,*c*_{t}): Express the boolean function*f*as a circuit*C*with XOR and AND gates. Let C^{†}be the same circuit as*C*, but with XOR and AND gates replaced by addition and multiplication gates over the integers. Let*f*^{†}be the multivariate polynomial that corresponds to*C*^{†}. Output*c*←*f*^{†}(*c*_{1}, ...,*c*_{t}).

Let us check that ciphertexts output by Evaluate_{ε} decrypt correctly. As a warm-up, let us consider Mult_{ε}. Let *c* = *c*_{1} · *c*_{2}, where *c*_{i}'s noise is *m*'_{i}, which has the same parity as the message *m*_{i}. We have that

for some integer *q'*. As long as the noises are small enough so that | *m*'_{1} · *m*'_{2} |< *p*/2, we have that

and therefore (*c* mod *p*) mod 2 = *m*_{1} · *m*_{2}, as it should be. We will consider the evaluation of more complicated functions momentarily, in Section 3.3.

So far we only described a symmetric homomorphic encryption scheme. Turning it into a public-key scheme is easy, but adds some complexity. As before, the secret key is *p*. The public key consists of a list of integers that are essentially "encryptions of zero." The list has length polynomial in λ. To encrypt a bit *m*, the ciphertext *c* is (essentially) *m* plus a random subset sum of the ciphertexts in the public key. If these ciphertexts have very small noise, the resulting ciphertext will also have small noise, and decryption will work properly: (*c* mod *p*) mod 2 will equal *m*, as before.

**3.3. How homomorphic is it?**

What is the set of permitted functions that our homomorphic encryption scheme ε can handle?

To answer this question, we need to analyze how the noise grows as we add and multiply ciphertexts. Encrypt_{ε} outputs a *fresh* ciphertext with a small noise, at most *N* bits. As we Add_{ε}, Sub_{ε}, or Mult_{ε} ciphertexts, the output ciphertext becomes more noisy. Multiplication tends to increase the noise faster than addition or subtraction. In particular, for ciphertexts *c*_{1} and *c*_{2} with *k*_{1}- and *k*_{2}-bit noises, the ciphertext *c* ← *c*_{1} · *c*_{2} has (roughly) (*k*_{1} + *k*_{2})-bit noise.

What happens when we perform *many* Add_{ε}, Sub_{ε}, and Mult_{ε} operations, as prescribed by the circuit representing a function *f*? Similar to what we saw above with multiplication, we have

for some integer *q'*, where *m*'_{t} is the noise associated to *c*_{i}. If |*f*^{†}(*m'*_{1}, ..., *m*'_{t})| < *p*/2, then (*f*^{†}(*c*_{1}, ..., *c*_{t}) mod *p*) equals *f*^{†}(*m'*_{1}, ..., *m*'_{t}). And if we reduce this result modulo 2, we obtain the correct result: *f*(*m*_{1}, ..., *m*_{t}).

In short, the functions that ε can handle are those for which |*f*^{†} (*a*_{1}, ..., *a*_{t})| is *always* less than *p*/2 if all of the *a*_{i} are at most *N* bits.

ε is already quite powerful. As an example, it can handle an elementary symmetric polynomial of degree *d* in *t* variables, as long as 2^{Nd} · < *p*/2, which is true (roughly) when *d* < *P*/(*N* · log *t*). For our suggested parameters, this degree can be quite large: λ/(log *t*) = Ω(λ/log λ). That ε can evaluate polynomials of such high degree makes it "homomorphic enough" for many applications. For example, it works well when *f* is a highly parallelizable functione.g., a basic keyword searchin which case *f* has fairly low degree.

**3.4. Semantic security and approximate GCDs**

Euclid showed that, given two integers *x*_{1} and *x*_{2}, it is easy to compute their greatest common divisor (gcd). But suppose that *x*_{1} = *s*_{1} + *p* · *q*_{1} and *x*_{2} = *s*_{2} + *p* · *q*_{2} are *near*-multiples of *p*, with *s*_{1} and *s*_{2} much smaller than *p*. When *p* is only an approximate gcd, is it still possible to compute *p* efficientlyi.e., in time polynomial in the bit-lengths of *x*_{1} and *x*_{2}? Not in general, as far as we know.

In fact, if we sample *s*_{i}, *p* and *q*_{i} with λ, λ^{2}, and λ^{5} bits (similar to our scheme ε), then the *approximate gcd problem* seems to remain hard even if we are given arbitrarily many samples *x*_{i} = *s*_{i} + *p* · *q*_{i}, rather than just two. For these parameters, known attacksincluding those using continued fractions and simultaneous diophantine approximationtake time essentially exponential in λ.

Moreover, we can reduce the approximate gcd problem to the security of our somewhat homomorphic encryption scheme. That is, we can prove that an attacker cannot efficiently break the semantic security of our encryption scheme unless the approximate gcd problem is easy.

**4.1. Alice's eureka moment**

One night, Alice dreams of immense riches, caverns piled high with silver, gold, and diamonds. Then, a giant dragon devours the riches and begins to eat its own tail! She awakes with a feeling of peace. As she tries to make sense of her dream, she realizes that she has the solution to her problem. She knows how to use her defective boxes to securely delegate the assembly of even the most intricate pieces!

Like before, she gives a worker a glovebox, box #1, containing the raw materials. But she also gives him several additional gloveboxes, where box #2 contains (locked inside) the key to box #1, box #3 contains the key to box #2, and so on. To assemble an intricate design, the worker manipulates the materials in box #1 until the gloves stiffen. Then, he places box #1 inside box #2, where the latter box already contains a the key to box #1. Using the gloves for box #2, he opens box #1 with the key, extracts the partially assembled trinket, and continues the assembly within box #2 until its gloves stiffen. He then places box #2 inside box #3, and so on. When the worker finally finishes his assembly inside box #*n*, he hands the box to Alice.

Of course, Alice observes, this trick does not work unless the worker can open box #*i* within box #(*i* + 1), and still have time to make a little bit of progress on the assembly, all before the gloves of box #(*i* + 1) stiffen. But as long as the unlocking operation (plus a little bit of assembly work) takes less than a minute, and as long as she has enough defective gloveboxes, then it is possible to assemble any piece, no matter how complicated!

**4.2. A dream deciphered**

In the analogy, the defective gloveboxes represent our somewhat homomorphic encryption scheme, which can perform Add, Sub, and Mult operations on ciphertexts for a little whileit can handle functions in a limited set until the noise becomes too large. What we would like to do is use this somewhat homomorphic scheme to construct a fully homomorphic one.

As before, box #1 with the precious materials inside represents the ciphertexts that encrypt the initial data. Box #(*i* + 1) with the key for box *i* inside represents an *encrypted secret decryption key*i.e., sk_{i} encrypted under pk_{i+1}.

In the analogy, Alice discovers that there is only one thing that her workers really need to be able to do in less than 1 min with the gloves, aside from performing a very small operation on the piece: unlock box #*i* within box #(*i* + 1) and extract the piece. It will turn out that there is only one function that our scheme ε really needs to be able to handle, with a tiny bit of room left over to perform one more Add, Sub, or Mult: the decryption function (which is like unlocking the "encryption box").

If ε has this self-referential property of being able to handle its own decryption function (augmented by a single gate), we say that it is *bootstrappable*. As we will show, if ε is bootstrappable, then one can use ε to construct a fully homomorphic encryption scheme ε^{†}.

**4.3. Bootstrappable to fully homomorphic**

Suppose that ε is bootstrappable. In particular, suppose that ε can handle the following four functions: the decryption function, expressed as a circuit *D*_{ε} of size polynomial in λ, as well as *D*_{ε} augmented by an Add, Sub, or Mult gate modulo 2. (*D*_{ε} augmented by Add consists of two copies of *D*_{ε} connected by an Add gate.) We will show that this is a *complete* set of circuits, in the sense that if these four circuits are in , then one can construct from ε a scheme ε^{†} that is fully homomorphic.

As a warm-up, suppose that ciphertext *c*_{1} encrypts the bit *m* under key pk_{1}. Suppose also that we have an encrypted secret key: let be a vector of ciphertexts that encrypt the bits of sk_{1} under pk_{2} via Encrypt_{ε}(pk_{2}, sk_{1j}). Consider the following algorithm.

Recrypt_{ε}(pk_{2}, *D*_{ε}, , *c*_{1}).

- Generate via Encrypt
_{ε}(pk_{2},*c*_{1j}) over the bits of*c*_{1} - Output
*c*← Evaluate_{ε}(pk_{2},*D*_{ε}, sk_{1}, )

The decryption circuit *D*_{ε} has input wires for the bits of a secret key and the bits of a ciphertext. Above, Evaluate_{ε} takes in the bits of sk_{1} and *c*_{1}, each encrypted under pk_{2}. Then, ε is used to evaluate the decryption circuit homomorphically. As long as ε can handle *D*_{ε}, the output *c* is an encryption under pk_{2} of Decrypt_{ε}(sk_{1}, *c*_{1}) = *m*. Recrypt_{ε} therefore outputs a new encryption of *m*, but under pk_{2}.

One fascinating thing about Recrypt_{ε} is that the message *m* is doubly encrypted at one point, first under pk_{1} and next under pk_{2}. Ordinarily, the only thing one can do with a doubly encrypted message is to peel off the outer encryption first, and then decrypt the inner layer. However, in Recrypt_{ε}, the Evaluate_{ε} algorithm is used to remove the *inner* encryption, just like Alice unlocks box #*i* while it is inside box #(*i* + 1).

It is also useful to imagine that ε is our somewhat homomorphic encryption scheme from Section 3, and consider what Recrypt_{ε} does to the noise of the ciphertexts. Evaluating *D*_{ε} removes the noise associated to the first ciphertext under pk_{1} (because, of course, decryption removes noise), but Evaluate_{ε} simultaneously introduces new noise while evaluating the ciphertexts under pk_{2}. As long as the new noise added is less than the old noise removed, we have made "progress." A similar situation holds in Alice's jewelry store. When the worker extracts the piece from the used-up glovebox #*i*, this process simultaneously uses up the gloves of box #(*i* + 1). We have made "progress" as long as the process does not leave box #(*i* + 1)'s gloves completely used-up.

Of course, our goal is to perform actual operations on underlying messages, not merely to obtain a new encryption of the same message. So, suppose that ε can handle *D*_{ε} augmented by some gatee.g., Add; call this augmented circuit *D*_{Add}. If *c*_{1} and *c*_{2} are two ciphertexts that encrypt *m*_{1} and *m*_{2}, respectively, under pk_{1}, and we compute and as before, as ciphertexts encrypting the bits of the ciphertexts under pk_{2}, then we have that

is an encryption under pk_{2} of *m*_{1} *m*_{2}.

By recursing this process, we get a fully homomorphic encryption scheme. The public key in ε^{†} consists of a sequence of public keys (pk_{1}, ..., pk_{l+1}) and a chain of encrypted secret keys , ..., , where sk_{i} is encrypted under pk_{i+1}. To evaluate a function *f* in ε^{†}, we express *f* as a circuit, topologically arrange its gates into levels, and step through the levels sequentially. For a gate at level *i* + 1 (e.g., an Add gate), we take as input the encrypted secret key and a couple of ciphertexts associated to output wires at level *i* that are under pk_{i}, and we homomorphically evaluate *D*_{Add} to get a ciphertext under pk_{i+1} associated to a wire at level *i* + 1. Finally, we output the ciphertext associated to the output wire of *f.*

Putting the encrypted secret key bits , ..., in ε^{†}'s public key is not a problem for security. These encrypted secret-key bits are indistinguishable from encryptions of 0 as long as ε is semantically secure.

**4.4. Circular security**

Strictly speaking, ε^{†} does not *quite* meet our definition of fully homomorphic encryption, since the complexity of KeyGen_{ε†} grows linearly with the maximum circuit depth we want to evaluate. (Fortunately, Encrypt_{ε†} and Decrypt_{ε†} do not depend at all on the function *f* being evaluated.)

However, suppose that ε is not only bootstrappable, but also *circular-secure*that is, it is "safe" to reveal the encryption of a secret key sk_{i} under its own associated public key pk_{i}. Then, we can simplify KeyGen_{ε}^{†}. We do not need distinct public keys pk_{i} for each circuit level and an acyclic chain of encrypted secret keys. Instead, the public key in ε^{†} can consist merely of a single public key pk and a single encrypted secret key (sk under pk), where pk is associated to all levels of the circuit. This approach has the additional advantage that we do not need to decide beforehand the maximal circuit depth complexity of the functions that we want to be able to evaluate.

For most encryption schemes, including our somewhat homomorphic scheme (as far as we know), revealing an encryption of sk under pk does not lead to any attack. However, it is typically difficult to *prove* that an encryption scheme is circular-secure.

The issue of circular security also fits within our physical analogy. Suppose that a key is locked inside the very same box that the key could open from the outside. Is it possible to use the gloves and key to open the box *from the inside*? If so, it would be a strange lock. Similarly, encryption schemes that are insecure in this setting tend to be contrived.

Is our somewhat homomorphic encryption scheme from Section 3 already bootstrappable? Can it handle its own decryption circuit? Unfortunately, as far as we can tell, ε can *almost* handle *D*_{ε}, but not quite. So, we modify ε slightly, constructing a new (but closely related) somewhat homomorphic scheme ε* that can handle essentially the same functions that ε can, but whose decryption circuit is simple enough to make ε* bootstrappable.

**5.1. Alice gets her hands dirty**

After her dream, Alice rushes to her store to see if her idea works. She locks box #1 and puts it inside box #2. Working with the gloves of box #2, she tries to unlock box #1 in less than 1 min. The thickness of the gloves and the stickiness of the lock combine to make it impossible.

She is despondent until she remembers that she has a special grease that makes her locks less sticky. This time, she locks box #3 and puts it inside box #4. She also puts her bottle of grease inside box #4. Working with the gloves of box #4, she squirts some grease on the lock and then tries to unlock it. But the gloves stiffen before she can finish.

Then, she thinks: why didn't I grease the box's lock *before* putting it inside the other box? That way, I wouldn't waste my valuable time with the gloves greasing the lock.

She locks box #5, greases its lock, and then puts it inside box #6. Working with gloves, she tries the lock again. This time it works, despite the clumsiness of the gloves!

At last, she has a system that lets her securely delegate the processing of her precious materials into arbitrarily complicated pieces! Her workers just need to apply the grease to each box before they put it inside the next box. She can hardly wait to put the system in place the following morning.

**5.2. Greasing the decryption circuit**

In our somewhat homomorphic encryption scheme ε from Section 3, the decryption function is:

Equivalently, but more simply, the equation is:

where LSB takes the least significant bit and ·⌉ rounds to the nearest integer. This is equivalent, since (*c* mod *p*) = *c − p* · *c/p*⌉. Since *p* is odd, we have that (*c* mod *p*) mod 2 = *c* − *c/p*⌉ mod 2. This is just the XOR of the least significant bits of *c* and *c/p*⌉.

In the decryption circuit *D*_{ε}, computing the LSB is immediate: the circuit simply does not have output wires for the more significant bits. Computing an XOR also takes only one gate. If the decryption function is complicated, it must be because computing *c/p*⌉ is complicated. Is the function *f*(*p, c*) = *c/p*⌉ (with the few steps afterward) something that ε can handle? If so, ε is bootstrappable, and can be used to construct a fully homomorphic encryption scheme.

Unfortunately, even a single multiplication of long numbersnamely, *c* with 1/*p*seems to be too complex for ε to handle. The reason is that *c* and 1/*p* each need to be expressed with at least *P* log *p* bits of precision to ensure that *f*(*p, c*) is computed correctly. When you multiply two *P*-bit numbers, a bit of the result may be a high-degree polynomial of the input bits; this degree is also roughly *P*. We saw that ε can handle an elementary symmetric polynomial in *t* variables of degree (roughly) *d < P*/(*N* · log *t*). However, ε cannot handle even a single monomial of degree *P*, where the noise of output ciphertext is upper-bounded by (2^{N})^{P} p^{N} *p*/2. Consequently, ε does not seem to be bootstrappable.

However, if we are willing to get our hands dirty by tinkering with ε to make the decryption function simpler, we eventually get a scheme ε* that is bootstrappable. The main idea of the transformation is to replace ε's decryption function, which multiplies two long numbers, with a decryption function that adds a fairly small set of numbers. In terms of the bits of the addends, this summation corresponds to a polynomial of fairly low degree that ε* can handle.

Let us go through the transformation step by step, beginning with KeyGen_{ε*}. The transformation uses a couple of integer parameters: 0 < α < β.

- KeyGen
_{ε*}(λ): Run KeyGen_{ε}(λ) to obtain keys (pk, sk), where sk is an odd integer*p*. Generate a set = ⟨*y*_{1}, ...,*y*_{β}⟩ of rational numbers in [0, 2) such that there is a sparse subset*S*⊂ {1, ..., β} of size α with Σ_{is}*y*_{i}1/*p*mod 2. Set sk* to be the sparse subset*S*, encoded as a vector*s*{0, 1}^{β}with Hamming weight α. Set pk* ← (pk, ).

The important difference between KeyGen_{ε*} and KeyGen_{ε} is that KeyGen_{ε*} includes a *hint* about the secret integer *p*namely, a set of numbers that contains a (hidden) sparse subset that sums to 1/*p* (to within a very small error, and up to addition by an even number). This hint is the "grease," which will be used in Encrypt_{ε*} and Decrypt_{ε*}. Although it is technically not the decryption key sk*, the integer *p* still can be used to decrypt a ciphertext output by Encrypt_{ε*}, so revealing this hint obviously impacts security, a point we elaborate on in Section 5.4.

- Encrypt
_{ε*}(pk*,*m*): Run Encrypt_{ε}(pk,*m*) to obtain ciphertext*c*. For*i*{1, ..., β}, set*z*_{i}←*c*·*y*_{i}mod 2 keeping only about log α bits of precision after the binary point for each*z*_{i}. The ciphertext*c** consists of*c*and = ⟨*z*_{1}, ...,*z*_{β}⟩.

The important point here is that the hint is used to *postprocess* a ciphertext *c* output by Encrypt_{ε}, with the objective of leaving less work remaining for Decrypt_{ε*} to do.

This sort of two-phase approach to decryption has been used before in *server-aided cryptography*. (See cites in Gentry^{2}.) In that setting, a user wants to minimize its cryptographic computatione.g., because it is using a constrained device, such as a smartcard or handheld. So, it outsources expensive computations to a server. To set up this arrangement, the user (in some schemes) must give the server a hint that is statistically dependent on its secret key sk, but which is not sufficient to permit the server to decrypt efficiently on its own. The server uses the hint to process a ciphertext directed to the user, leaving less work for the user to do. In our setting, the encrypter or evaluator plays the role of the server, postprocessing the ciphertext so as to leave less work for the decryption algorithm to do.

- Decrypt
_{ε*}(sk*,*c**): Output LSB(*c*) XOR LSB(Σ_{i}*s*_{i}*z*_{i}⌉). Decryption works, since (up to small precision errors) Σ_{i}*s*_{i}*z*_{i}= Σ_{i}*c*·*s*_{i}*y*_{i}=*c/p*mod 2.

To ensure that the rounding is correct despite the low precision, we need *c* to be closer (than the trivial *p*/2) to a multiple of *p* (say, within *p*/16). This makes smaller than , since is limited to functions where |*f*(*a*_{1}, ..., *a*_{t})| < *p*/16 when the *a*_{i} are *N* bits. This makes only a small difference.

The important point regarding Decrypt_{ε*} is that we replace the multiplication of *c* and 1/*p* with a summation that contains only α nonzero terms. The bits of this summation can be computed by a polynomial of degree α · polylog(α), which ε* can handle if we set α to be small enough.

- Add
_{ε*}(pk*,*c**_{1},*c**_{2}): Extract*c*_{1}and*c*_{2}from*c**_{1}and*c**_{2}. Run*c*← Add_{ε}(pk,*c*_{1},*c*_{2}). The output ciphertext*c** consists of*c*, together with the result of postprocessing*c*with · Mult_{ε*}(pk*,*c**_{1},*c**_{2}) is analogous.

**5.3. How to add numbers**

To see that ε* can handle the decryption function plus an additional gate when α is set small enough, let us consider the computation of the sum Σ_{i} s_{i} z_{i}. In this sum, we have β numbers *a*_{1}, ..., *a*_{β}, each *a*_{i} expressed in binary (*a*_{i,0}, ..., *a*_{i,−l}) with *l* = O(log α), where at most α of the *a*_{i}'s are nonzero (since the Hamming weight of *s* is α). We want to express each bit of the output as a polynomial of the input bits, while minimizing the degree of the polynomial and the number of monomials.

Our approach to the problem is to add up the column of LSBs of the numberscomputing the Hamming weight of this columnto obtain a number in binary representation. Then, we add up the column of penultimate bits, etc. Afterward, we combine the partial results. More precisely, for *j* [0, −*l*], we compute the Hamming weight *b*_{j}, represented in binary, of (*a*_{1,j}, ..., *a*_{βj}). Then, we add up the *l* + 1 numbers *b*_{0}, ..., 2^{−l}b_{−l} to obtain the final correct sum.

Conveniently, the binary representation of the Hamming weight of any vector {0,1}^{t} is given by

where *e*_{i}(*x*_{1}, ..., *x*_{t}) is the *i*th elementary symmetric polynomial over *x*_{1}, ..., *x*_{t}. These polynomials have degree at most *t*. Also, we know how to efficiently evaluate the elementary symmetric polynomials. They are simply coefficients of the polynomial *p*(*z*) = Π^{t}_{i=1} (*z − x*_{i}). An important point is that, in our case, we only need to evaluate the polynomials up to degree α, since we know a priori that each of the Hamming weights is at most α. We saw in Section 3.3 that we can handle elementary symmetric polynomials in *t* variables of degree up to about λ/log *t* = Ω(λ/log λ) for our suggested parameters. We can set α to be smaller than this.

The final step of computing the sum of the *b*_{j}'s does not require much computation, since there are only *l* + 1 = *O*(log α) of them. We get that a ciphertext encrypting a bit of the overall sum has noise of at most *N* · α · *g*(log α) bits for some polynomial *g* of low degree. If the final sum modulo 2 is (*b'*_{0}, *b'*_{−1}, ...) in binary, then the rounding operation modulo 2 is simply *b'*_{0} XOR *b'*_{−1}. With the additional XOR operation in decryption, and possibly one more gate, the noise after evaluating the decryption function plus a gate has at most *N* · α · *h*(log α) bits for some polynomial *h*.

The scheme ε* becomes bootstrappable when this noise has at most log(*p*/16) = *P* − 4 bits. For example, this works when α = λ/polylog(λ), *N* = λ, and *P* = λ^{2}.

**5.4. Security of the transformed scheme**

The encryption key of ε* contains a hint about the secret *p*. But we can prove that ε* is semantically secure, unless either it is easy to break the semantic security of ε (which implies that the approximate gcd problem is easy), or the following sparse (or low-weight) subset sum problem (SSSP) is easy: given a set of β numbers and another number *s*, find the sparse (α-element) subset of whose sum is *s*.

The SSSP has been studied before in connection with server-aided cryptosystems. If α and β are set appropriately, the SSSP is a hard problem, as far as we know. In particular, if we set α to be about λ, it is hard to find the sparse subset by "brute force," since there are (β_{α}) β^{α} possibilities. If the sparse subset sum is much closer to 1/*p* than any other subset sum, the problem yields to a lattice attack. But these attacks fail when we set β large enough (but still polynomial in λ) so that an *exponential* (in λ) number of subset sums are as close to 1/*p* as the sparse subset. Concretely, we can set β = λ^{5} · polylog(λ).

We now know that FHE is possible. We already have the scheme presented here, the lattice-based scheme by Gentry,^{2,3} and a recent scheme by Smart and Vercauteren.^{7}

There is still work to be done toward making FHE truly practical. Currently, all known FHE schemes follow the blueprint above: construct a bootstrappable somewhat homomorphic encryption scheme ε, and obtain FHE by running Evaluate_{ε} on ε's decryption function. But this approach is computationally expensive. Not only is the decryption function expressed (somewhat inefficiently) as a circuit, but then Evaluate_{ε} replaces each bit in this circuit with a large ciphertext that encrypts that bit. Perhaps someone will find a more efficient blueprint.

The scheme presented here, while conceptually simpler, seems to be less efficient than the lattice-based scheme. To get 2^{λ} security against known attackse.g., on the the approximate gcd problemciphertexts are λ^{5} · polylog(λ) bits, which leads to λ^{10} · polylog(λ) computation to evaluate the decryption function. The lattice-based scheme with comparable security has λ^{6} · polylog(λ) computation. This is high, but not totally unreasonable. Consider: to make RSA 2^{λ}-secure against known attacksin particular, against the number field sieve factoring algorithmyou need to use an RSA modulus with approximately λ^{3} bits. Then, RSA decryption involves exponentiation by a λ^{3}-bit exponenti.e., about λ^{3} multiplications. Even if one uses fast Fourier multiplication, this exponentiation requires λ^{6} · polylog(λ) computation. Also, unlike RSA, the decryption function in our scheme is highly parallelizable, which may make an enormous difference in some implementations.

The morning after her dream, Alice explains her glovebox solution to her workers. They are not happy, but they wish to remain employed. As the day progresses, it becomes clear that the gloveboxes are slowing down the pace of jewelry construction considerably. The main problem seems to be the thick gloves, which multiply the time needed for each assembly step. After a few days of low output, Alice curtails her use of the gloveboxes to pieces that contain the most valuable diamonds.

Alice loses her suit against Acme Glovebox Company, because, as far as anyone knows in Alice's parallel world, gloves in gloveboxes are always very stiff and stiffen completely after moderate use. The old judge explains this to her in a patronizing tone.

But Alice refuses to give up. She hires a handsome young glovebox researcher, and tasks him with developing a glove flexible enough to permit the nimble assembly of jewels and unlocking of boxes, but sturdy enough to prevent the boxes from being easily compromised. The researcher, amazed at his good fortune, plunges into the problem.

1. Boneh, D., Lipton, R.J. Algorithms for black-box fields and their application to cryptography (extended abstract). In *CRYPT* (1996), 283297.

2. Gentry, C. *A fully Homomorphic Encryption Scheme.* Ph.D. thesis, Stanford University, 2009. crypto.stanford.edu/craig.

3. Gentry, C. Fully homomorphic encryption using ideal lattices. *STOC.* M. Mitzenmacher ed. ACM, 2009, 169178.

4. Goldwasser, S., Micali, S. Probabilistic encryption. *J. Comp. Syst. Sci. 28*, 2 (1984), 270299.

5. Rivest, R.L., Adleman, L.M., Dertouzos, M.L. On data banks and privacy homomorphisms. In *Foundations of Secure Computations* (1978), 169180.

6. Rivest, R.L., Shamir, A., Adleman, L.M. A method for obtaining digital signatures and public-key cryptosystems. *Commun. ACM 21*, 2 (1978), 120126.

7. Smart, N.P., Vercauteren, F. Fully homomorphic encryption with relatively small key and ciphertext sizes, 2009. http://eprint.iacr.org/2009/571.

8. van Dam, W., Hallgren, S., Ip, L. Quantum algorithms for some hidden shift problems. *SIAM J. Comp. 36*, 3 (2006), 763778.

9. van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V. Fully homomorphic encryption over the integers, 2009. http://eprint.iacr.org/2009/616.

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.

DOI: http://doi.acm.org/10.1145/1666420.1666444

**©2010 ACM 0001-0782/10/0300 $10.00**

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.

No entries found