# The Swiss Army Knife of Cryptography

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.

## 15 thoughts on “The Swiss Army Knife of Cryptography”

1. miforbes says:

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?

1. Boaz Barak says:

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}

2. Orit says:

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.

1. Boaz Barak says:

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

2. miforbes says:

Ah, ok. Thanks

3. Orit says:

in the lecture notes are mentioned few other uses of HE such as e-voting, e-auction, etc…
What is the encryption scheme in these problems? I assume we need an asymmetric encryption, but is there one secret key and multiple public keys? Or some other configuration?

1. Boaz Barak says:

It is possible to get in a blackbox manner the encryptions scheme with stronger properties from the basic FHE, though there are more efficient ways to do it, see for example this paper http://tau.ac.il/~tromer/papers/tfhe-mpc.pdf

4. Peihan says:

The construction of two party secure computation from FHE seems to be problematic even in the semi-honest case. FHE doesn’t guarantee that the function f(\cdot, y) is hidden to Alice if Alice holds the secret key. In other words, E(f(x,y)) is only semantically secure to an adversary without the secret key, but not necessarily to Alice. In fact, in the concrete constructions of FHE, Alice might figure out some information about y given the noise in E(f(x,y)). Does that make sense?

1. Boaz Barak says:

As in my lecture notes this is based on, we assumed here an FHE that has a “rerandomization” property where if you homomorphically apply a NAND gate to E(a) and E(b) then you get a ciphertext that is statistically indistinguishable from E(a NAND b), because it is statistically indistinguishable it is even secure against someone holding the secret key. The known constructions have this property.

1. Peihan says:

The “re-randomization” property is not necessarily true for FHE, right? You need the guarantee that a freshly generated ciphertext is indistinguishable from a ciphertext computed from E(a) and E(b), even given the secret key and the randomness of generating E(a) and E(b). Is there a generic way to transform any FHE scheme into a “re-randomizable” one?

2. Boaz Barak says:

This property is true for many (all?) known constructions but I don’t know if there is a generic transformation. I think the construction of Rothblum’s paper ( http://eccc.hpi-web.de/report/2010/146/ ) comes close.

That paper shows that without loss of generality in an FHE the public key is a bunch of encryptions of 0 and 1 and you homomorphically combine them to obtain a fresh encryption. That suggests an approach for re-randomizing a ciphertext c by combining it with those encryptions but you might need some assumptions to argue that this is statistically close to a fresh encryption.