Guest post by Boaz Barak and Zvika Brakerski

In 2009, Craig Gentry shook the world of cryptography by presenting a construction of a Fully Homomorphic Encryption Scheme (FHE). In this post and the next one, we will explain what FHE is, why cryptographers are so excited about it, and how its construction works.

There is a common wisdom in theoretical computer science that if someone gives a polynomial-time algorithm for some natural problem, then even if the initial exponent is some huge number such as ${n^{17}}$, eventually it will be improved to some more reasonable running time such as ${n^2}$. While this is not always the case, this wisdom definitely held true in the case of FHE, where followup works to Gentry have used the same general blueprint but improved the original construction in a number of dimensions. The running time has improved from roughly ${n^8}$ (for security ${2^n}$) to ${\Tilde{O}(n)}$ (the scheme has even been implemented and optimized, though much work remains to be done to make it truly practical.) The computational assumptions used have been weakened to standard ones used for prior “plain” (i.e., non-homomorphic) encryption schemes. And the schemes have been simplified enough so that their description can fit, well, in a blog post…

What is a fully homomorphic encryption scheme?

A fully homomorphic encryption scheme is an encryption that allows to take encryptions ${E(a)}$ and ${E(b)}$ of two bits ${a,b}$ and obtain from them encryptions of ${NOT(a)}$, ${a\; AND\; b}$ and ${a\; OR\; b}$. Clearly, this means that given a (bit by bit) encryption ${E(x)}$ of some string ${x}$, we can compute ${E(f(x))}$ where ${f}$ is any Boolean circuit of our choice. The crucial point is that these transformations should be done without using the secret key.

Why is this useful?

This example is cool, but is not the only reason why FHE is important. The main reason cryptographers (or at least we) are excited about FHE is that it is kind of the “ultimate cryptographic tool”. Of course FHE does not solve all the world’s crypto problems, and in fact for many of the problems it does solve there exist non FHE-based solutions that are more efficient or based on weaker assumptions. But the FHE-based constructions are often conceptually simpler, and in particular FHE gives a unified way to achieve cryptographic notions such as multiparty secure computation, private information retrieval, electronic voting, zero knowledge, and more. For this reason, we believe that FHE (and some of its corollaries) should be taught in any introduction to cryptography course. Sure, the construction may not be practical right now, but the reason we teach advanced topics in a crypto course is not for the students to learn how to implement, say, electronic voting. It is to open the students’ minds to the amazing possibilities in cryptography, where constructions exists for almost every concept you could imagine (and some that a-priori you wouldn’t dare to even imagine…). And, frankly, we also teach such topics to give the students the treat of seeing some cool stuff, after slogging through security definitions and reductions all term long :)

To demonstrate this point, in the rest of this post we show how one can use fully homomorphic encryption to easily achieve two canonical cryptographic tools- two party secure computation and zero knowledge proof systems. In the next post we’ll give a complete account on how to construct an FHE scheme.

Two party secure computation from FHE.

To demonstrate how FHE yields canonical previous results in a conceptually clean way, lets consider the task of two party secure computation. In this setting, Alice and Bob hold inputs ${x,y}$ respectively, and wish to compute some function ${f(x,y)}$ of their inputs, with the important restriction that Alice should not learn anything about ${y}$ beyond the output ${f(x,y)}$, and similarly Bob should not learn any unnecessary information about ${x}$. Two party secure computation (and its generalization to ${k>2}$ parties) is an extremely general concept, capturing a great many cryptographic applications. For example, multi-party computation allows Danish sugar beet farmers to participate in an auction to sell their beets without revealing their private supply/demand curve, or banks to compute their aggregate risk profile without revealing proprietary portfolio information. Indeed, almost any cryptographic task can be cast into this very general framework.

Here is how you could achieve 2-party secure computation using fully homomorphic encryption:

1. Alice generates keys for a FHE, and sends ${c=E(x)}$ to Bob.
2. Bob runs the homomorphic evaluation on ${c}$ to compute ${c'=E(f(x,y))}$, and sends ${c'}$ to Alice.
3. Alice decrypts ${c'}$ and sends to Bob the answer.

The idea is that Bob only sees an encryption of ${x}$, while Alice never actually sees ${y}$ but only (encryption of) ${f(x,y)}$, and so they both learn only the output ${f(x,y)}$. Of course, a moment’s thought shows that this protocol has some problems— how can we tell that Bob computes ${f}$ on ${c}$ and not some other function? and how are we sure that Alice decrypted ${c'}$ correctly? Indeed, this protocol only offers security in the so-called honest but curious model (which is already a non-trivial task, with known constructions taking at least a full lecture to cover). But, it can be converted into a fully secure protocol by having Bob offer a zero knowledge proof that he computed ${c'}$ correctly in Step 2, and Alice prove in zero knowledge that she sent a valid decryption of ${c'}$ in Step 3. The zero knowledge proofs are used to guarantee that Bob and Alice execute their steps correctly, but (as their name implies) they reveal nothing about Alice and Bob’s private inputs, and so do not harm security. (Cryptographers might note another subtle point with this protocol is that to ensure security, we need the homomorphic encryption to satisfy a property known as “function privacy” or “rerandomization”; fortunately all known constructions of FHE can be modified to have this property.)

Zero knowledge proofs for NP have rather elegant constructions, but can also, as we describe below, be obtained directly using FHE. In particular, the FHE based construction does not go through the Cook-Levin Theorem and also has the advantage of being much more communication efficient than the standard (i.e., not PCP based) constructions of zero knowledge proofs. Indeed, notice that the communication in the protocol above only involved encryptions of the input ${x}$ and output ${f(x,y)}$. This is much more efficient than previous non-FHE-based construction of secure computation, that involved communication proportional to the number of gates required to compute the function ${f}$. In fact, using FHE one can transform any (non secure) protocol to compute ${f}$ into a secure protocol with only polylogarithmic overhead in the communication complexity. This is extremely useful in settings, such as the one we mentioned above, where one or both of the inputs can be very large databases, which we wouldn’t want to transmit between the two parties.

Zero knowledge proofs from FHE.

We now describe how Alice can use FHE to prove to Bob in zero knowledge that there exists some string ${w}$ such that ${g(w)=1}$, where ${g}$ is an arbitrary (efficiently computable) function. Here is our first cut for such a protocol:

1. Alice generates keys for a FHE, and sends ${c=E(w)}$ to Bob.
2. Bob runs the homomorphic evaluation on ${c}$ to compute ${c'=E(g(w))}$ and sends it to Alice.
3. Alice decrypts ${c'}$ and sends Bob the answer ${b}$. Bob checks that ${b=1}$.

Once more, our first cut is not good enough. How do we know that Alice doesn’t always send ${1}$ to Bob? And how are we sure that Bob computes ${c'}$ correctly, rather than using it to ask Alice to decrypt, say, the first bit of ${w}$?

Fortunately, this problems can be remedied fairly easily. To fix the first problem, in the second step Bob can set ${c'}$ to be an encryption of ${0}$ with probability ${1/2}$, instead of ${E(g(w))}$. Then he’ll want to see that in the last step, Alice always returns the correct value of either ${0}$ or ${1}$ based on Bob’s random choice. This will ensure that if ${g(w)=0}$ then Bob will reject with probability at least ${1/2}$, which of course can be amplified by repetition.

We still didn’t solve Alice’s problem— how can she be sure that Bob actually computed ${c'}$ correctly (either by evaluating ${g}$ on it, or setting it to an encryption of ${0}$), rather than setting, say ${c'=E(w_1)}$? To do that, we modify the last step a bit. Instead of sending the answer ${b}$, Alice only sends a commitment to ${b}$. Then, we add an additional step in which Bob presents all the randomness he used in Step 2, allowing Alice to verify it was executed correctly, and only then Alice opens up the commitments to ${b}$. The new protocol can be shown to be secure. (One final subtlety is that, depending on how strongly we define FHE, the function privacy/rerandomization property may only hold if Alice chose the public parameters for the encryptions properly; this can be ensured by an initial “cut and choose” step, where Alice generates two sets of keys, and Bob chooses one to use for the protocol, while for the other Alice needs to reveal the corresponding secret keys and private randomness.)

What’s next

In the next post, we’ll move to the more exciting part: the actual construction of a fully homomorphic encryption scheme. The construction we show takes after Zvika’s recent scheme, which itself, of course, builds on a long sequence of works initiated by Gentry (and one might say even earlier works like those by Ajtai-Dwork, Goldreich-Goldwasser-Halevi, and Regev).

We were of course somewhat loose with the technical details in this blog post, but we’ll be happy to fill them up in comments below! Also, Boaz’s lecture notes (here, here, and there) contain some additional details.

1. May 1, 2012 11:21 pm

The lecture notes linked to indicate that the FHE scheme is public-key (this wasn’t clear on a first read of the blog post), and it seems like that property is crucial for the application to 2-party computation but not for the zero-knowledge proof. Is private-key FHE interesting? Easier to obtain?

May 2, 2012 1:57 am

Private key FHE is interesting and suffices for many applications. In fact, as we mention in the next post, there is a general transformation from private key FHE to public key FHE. For a scheme that has the rerandomization/function-privacy property this transformation is particularly easy. The public key is simply a pair of encryptions C_0 and C_1 encrypting 0 and 1 respectively, and to encrypt a bit sigma you send a rerandomized version of C_{sigma}

February 17, 2013 7:41 pm

Can you explain why the encryption scheme must be public in the case of the two party computation?
I can’t see the use of the public key in the evaluation process.

• March 26, 2013 11:03 pm

You are right, a private key FHE would work, but in fact for FHE the difference between private and public key is fairly minor.

May 2, 2012 2:18 am

Ah, ok. Thanks