Building the Swiss Army Knife
Guest post by Boaz Barak and Zvika Brakerski (part 2)
In the previous post, we demonstrated the versatility of fully homomorphic encryption and its applicability for multiple applications. In this post we will demonstrate (not too painfully, we hope) how fully homomorphic encryption is constructed. Our goal is to present the simplest solution that (we could think of and) works. We will not insist on achieving the best parameters or security guarantees, however the principles we describe are qualitatively the “state of the art” in FHE construction.
Let us get to work, then! We already explained in the previous post that in order to achieve full homomorphism, it is sufficient to homomorphically evaluate a universal set of gates. The universal set we will use is , also known as addition and multiplication over . (This is the “universal set of choice” for almost all known schemes.) This will allow us to evaluate any efficiently computable function by representing it as an arithmetic circuit over and performing homomorphic evaluation gate by gate. From this point and on, almost until the end of this post, we will thus forget about circuits and focus on homomorphic addition and multiplication modulo .
Encryption and Decryption
You would think that a homomorphic encryption scheme must be incredibly complicated, but in fact it is extremely simple. The secret key is a random binary vector and to encrypt a bit we output a random real vector satisfying
Here is the dot product , we write for and denotes the number such that for some integer (e.g., and ). The numbers are parameters of the system and are related to its security. Of course we won’t actually work with real numbers, but truncate them to some finite precision (this all works out as you would expect).
Given , it is not hard to generate such a random vector , and of course as long as , Equation (1) also yields a decryption algorithm (just compute the dot product and round the answer). You may have noticed that we need the key for both encryption and decryption. We thus get a symmetric key encryption scheme, rather than a public key scheme (where the encryption can be done using a different, public, key). However, this is not an issue since a homomorphic symmetric scheme implies a public key scheme with similar parameters. Therefore we can conveniently focus on the symmetric case.
Is this scheme secure?
That is an excellent question. For example, observe that if is equal to , then this scheme is not secure. Indeed in this case, given sufficiently many encryptions of , the secret key can be efficiently restored by simple Gaussian elimination. However, Gaussian elimination is a very “brittle” algorithm and if we inject even a relatively small amount of noise (e.g., set or ) then there is no known attack. In fact, the difficulty of solving noisy linear equations (in various settings and variants) underlies many cryptographic schemes as well as the famous learning parity with noise problem and its large alphabet cousin “learning with errors”. The scheme above is secure assuming a variant of the learning with errors problem, and so if you can break it, we (and a bunch of other people) will be happy to know!
Homomorphic Addition and Multiplication
We almost forgot that we are here to talk about homomorphism- lets try to see why our suggested scheme is homomorphic. Recall that for homomorphism, we are given two cyphertexts and encrypting and respectively and need to compute ciphertexts and that encrypt and respectively. The caveat is that of course we must perform these operations without access to the secret key.
Addition is easy. We can simply set . Now from Equation (1) we know that
where and are integers. So, if we add them together we’ll get that
or in other words,
That is, is indeed an encryption of (with twice as much noise, but that’s not too bad).
Multiplication is more tricky. To get some intuition, let us start by ignoring that we work mod and have noise, and pretend that the given ciphertexts and simply satisfy and . Even then it’s not at all clear how we would find a ciphertext satisfying . However, we do know one way to express in terms of and . Namely we have the equation
How can we use Equation (2) to create ? At this point we recall that even though the homomorphic operation cannot use the secret key, we are allowed to provide it with additional auxiliary information, so long as this information doesn’t violate security. (This is not cheating since the auxiliary information can either be a part of some public parameters/key, or simply concatenated to every encryption.) Specifically, suppose that we publish, a list of encryptions of the bits . Since these are encryptions, security is unharmed by making them public (more on this point later). However, if we keep to our blissful ignorance of noise and modulo factors, this means we can replace in Equation (2) the factors with , obtaining
Thus, we can set to obtain an encryption of .
Now let’s see what happens when we consider the modulo and noise factors. Equation (2) changes to
since (given that ) we know that . This is not so bad, since we assume is really tiny, and in particular much smaller than . However, now we need to consider these factors also in the encryptions . Namely, our guarantee will now be that for some and integer . Thus
Thus we would be done if was an integer. Unfortunately, we have no such guarantee, since are real vectors whose coordinates need not be integer. However, there is still something we can do. We consider the bit representation of the number . That is, let us write
where the numbers are in . We’ll stop at , which is more than enough precision for our needs. Now we’ll publish encryptions of the value (this is not a value, but our encryption is just as secure for encrypting arbitrary real numbers in as for encrypting bits). Our ciphertext will be defined as
Clearly, can be computed from and the encryptions . Now, writing , we can do a similar calculation as before to show that
for some integer . Thus is indeed an encryption of , albeit with higher noise level of .
Evaluating bounded depth circuits
So far we showed how to evaluate addition and multiplication, and get back to a ciphertext that looks the same as the one we started with. The only thing that should concern us is the growth of the noise in the process (recall that the noise magnitude has to stay under to guarantee correct decryption). We start with tiny noise of magnitude , but with each homomorphic operation, the noise grows by a factor of at most (a more careful look will show that the actual factor is actually , however suffices for our purposes). We now recall that our final goal is to evaluate a generic function that is represented by an arithmetic circuit over . If the circuit has depth , then the evaluation process increases the noise by a factor of . Therefore, in order to correctly decrypt, we must choose so that . Recall that we can allow to be sub-exponential, say , and so we can correctly evaluate circuits of depth up to .
To summarize, we did not achieve fully homomorphic encryption yet, but we did show how to evaluate any arithmetic circuit of depth at most . This could be sufficient if one wants to evaluate fairly shallow circuits. In fact, if the depth of the circuit is known ahead of time, we can choose large enough to allow homomorphism of the desired circuit (this only requires polynomial in ). The latter notion is sometimes called leveled-FHE.
Bootstrapping and Full Homomorphism.
Finally, we now show how to achieve “real” fully homomorphic encryption using Gentry’s bootstrapping technique. Specifically, we will show a method to reduce the noise level of ciphertexts. Given a ciphertext encrypting with a noise level that can be as large as, say, , this method yields another ciphertext encrypting the same bit but with a noise level at most . Again, this is done using only public information and without knowing . Given this tool, we can evaluate a circuit of any depth by periodically performing this bootstrapping operation whenever the noise becomes too large.
The (ingenious though somewhat confusing) idea behind bootstrapping is to homomorphically evaluate the decryption circuit itself. Given a ciphertext , we consider the function that maps into the decryption of using the key . Since decryption in our scheme is basically just an inner product, this is a function of the secret key which can be computed by a circuit of depth . (In fact it is a good exercise to show this can be done in depth.) This means that given an encryption of with noise level (which we can make available publicly without harming security), we can run homomorphically to obtain an encryption of , whose noise level will be . This completes the noise reduction, and viola – our hard labor resulted in fully homomorphic encryption!
A note on circular security. There were a few details we glossed over, and we’ll be happy to address them in the comments below. One issue is that the standard definition of security for encryption does not guarantee that it’s OK to publish encryptions of (functions of) the secret key, as we needed to do, and so one needs to assume a stronger notion known as key dependent message security. However, based on current knowledge, the assumption that our scheme satisfies this stronger notion seems very plausible. In fact, in Section 4.4 of his thesis Gentry gives a heuristic argument that any fully homomorphic encryption in fact enjoys such strong security, by showing this holds in the so called random oracle model. (Cryptographers might find this result surprising given that the encryption scheme does not use any hash function.) Nevertheless, showing a fully (non-leveled) homomorphic encryption from standard assumptions remains an important open problem.