# 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.

Clearly! Great blog. I am reading your paper “Lattice-Based FHE as Secure as PKE”. I want to know why did you use successive dimension-modulus reduction rather than once dimension-modulus reduction?

This post is fantastic, thanks. What I don’t understand, though, is why the demonstration with the multiplication (c.c’) is useful. Aren’t all computer operations based on binary addition, and linearity defined by addition also ? Why is it necessary to check it here ?

Well there are two reasons for that.

Firstly, it isn’t actually multiplication but really just an AND operation. The AND and the XOR together mean that this is “Turing complete” meaning that you can do ANY digital logic with it using only those two operations. For instance, you could make pacman with it now, or a web browser.

Secondly, yes multiplication is repeated addition, but if you are able to do multiplication homomorphically, it means that the person doing the multiplication doesn’t have to know what numbers are being multiplied.

With repeated addition, the person doing the math would need to know it was being multiplied by 3 (for example) and do that many additions. There are times where this is appropriate (where the algorithm being performed on the secret numbers requires a multiplication), but other times it isn’t appropriate. If you want to multiply two secret (encrypted) numbers, you don’t want the person doing the math to know what one of the numbers is, just so they can do the multiplication.

Thanks for the explanation ! I get it now.

Hello! Thanks for the awesome article. I seem to be stuck (or have a misunderstanding) about addition.

Let’s say that we have a key size of 1, where the key is [1] and we have three encrypted bits.

A = 0.01 (plain text was false)

B = -0.99 (plain text was true)

C = 0.99 (plain text was true).

If we want to perform A | B | C, (| is or), we do this:

A = (A + B) mod 2

A = (A + C) mod 2

When we actually do this, here’s what we get:

A = ( 0.01 – 0.99) = -0.98

A = (-0.98 + 0.99) = 0.01

If we decrypt that by rounding it to the nearest integer and then rounding it, we get 0 (false)

However… false OR true OR true should be true.

Where did i mis-step?

Thanks! (:

My mistake is that the addition is XOR, not OR. It’s working as it should be (of course!).