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 , eventually it will be improved to some more reasonable running time such as . 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 (for security ) to (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 and of two bits and obtain from them encryptions of , and . Clearly, this means that given a (bit by bit) encryption of some string , we can compute where 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?

As one example, suppose that you own a small business and store your sales database with some some cloud computing provider. (This blog’s editors can recommend one…) Since your data is confidential, you want to store it encrypted on the server. But now what happens when you’re at your phone and want to find out what were your average sales last year in zip code 02142? Since your data is encrypted, it seems you’d need to download your entire database, decrypt it, and perform this search, which kind of defeats the purpose of outsourcing your computation in the first place. With homomorphic encryption, the server can perform this computation on the encrypted database, and send you an encryption of the answer, without learning any information along the way.

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 respectively, and wish to compute some function of their inputs, with the important restriction that Alice should not learn anything about beyond the output , and similarly Bob should not learn any unnecessary information about . Two party secure computation (and its generalization to 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 to Bob.
2. Bob runs the homomorphic evaluation on to compute , and sends to Alice.
3. Alice decrypts and sends to Bob the answer.

The idea is that Bob only sees an encryption of , while Alice never actually sees but only (encryption of) , and so they both learn only the output . Of course, a moment’s thought shows that this protocol has some problems— how can we tell that Bob computes on and not some other function? and how are we sure that Alice decrypted 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 correctly in Step 2, and Alice prove in zero knowledge that she sent a valid decryption of 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 and output . 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 . In fact, using FHE one can transform any (non secure) protocol to compute 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 such that , where is an arbitrary (efficiently computable) function. Here is our first cut for such a protocol:

1. Alice generates keys for a FHE, and sends to Bob.
2. Bob runs the homomorphic evaluation on to compute and sends it to Alice.
3. Alice decrypts and sends Bob the answer . Bob checks that .

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

Fortunately, this problems can be remedied fairly easily. To fix the first problem, in the second step Bob can set to be an encryption of with probability , instead of . Then he’ll want to see that in the last step, Alice always returns the correct value of either or based on Bob’s random choice. This will ensure that if then Bob will reject with probability at least , 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 correctly (either by evaluating on it, or setting it to an encryption of ), rather than setting, say ? To do that, we modify the last step a bit. Instead of sending the answer , Alice only sends a commitment to . 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 . 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.