Are there simpler FHE methods than Craig Gentry's original paper?

Question

Craig Gentry's 2010 paper on FHE is very cool, and I'm planning on implementing a basic proof of concept FHE.

I was wondering though, are there any simpler methods that have been discovered since then?

The bootstrapping and the multiplication pre shared table would be nice to get rid of if possible. (I'm sure the whole world agrees, but is glad it can be done at all).

Anything simpler out there yet?

Here are the references I've found / have been using while trying to implement it. Note that I have been looking to implement it myself after understanding the theory, so haven't been looking for existing implementations, although definitely would look at them if having problems implementing.

http://windowsontheory.org/2012/05/01/the-swiss-army-knife-of-cryptography/

http://outsourcedbits.org/2012/06/26/applying-fully-homomorphic-encryption-part-1/

http://crypto.stanford.edu/craig/craig-thesis.pdf

http://researcher.watson.ibm.com/researcher/files/us-shaih/fhe-implementation.pdf

And then of course the links provided by people as comments in response to this question!

Answer 1

As you point out, there is the DHGV 2010 scheme over the integers based on the approximate GCD problem but asymptotics are not great with this scheme, for eg. one of the parameters for DHGV is around $2^{\mathcal{O}(\theta^{5})}$ where $\theta$ is the security parameter.

Of the so called second generation schemes, I would say that BGV has been pretty well benchmarked from a performance standpoint (https://people.csail.mit.edu/vinodv/6892-Fall2013/BGV.pdf) - BGV is based on hardness of lattice SVP (Gentry's original scheme, on the other hand was based on two hardness assumptions - the ideal coset and the sparse subset sum problems - additionally, it required some machinations around "squashing" the scheme's decryption circuit in order to make it boostrappable).

BGV is both "leveled" and bootstrappable and there is variant that utilizes Ring-LWE encryption with an "aggregate" plaintext space that consists of integer subrings of cyclotomic number fields $\mathbb{Z}[X]/\langle \Phi_m(X),p \rangle$ where $m$ is a power of 2. The Ring-LWE BGV variant also utilizes Smart and Vercauteren's application of "double" Chinese Remaindering as a structure theorem for it's aggregate plaintext space, thereby allowing for SIMD operations on the data - what this means is that the scheme allows one to encode multiple messages within "slots" in the aggregate plaintext space, and then perform parallel homomorphic Add and Multiply operations on the messages (https://eprint.iacr.org/2011/133). Also, since we're talking about encoding messages as polynomials, FFT can be utilized for fast multiplcation of ciphertext polynomials. Last but not least, BGV leverages automorphisms associated with the plaintext's cyclotomic number field to "permute" slots or elements without having to unpack the ciphertext - so the upshot of all of this is that BGV allows for pretty efficient homomorphic evaluation - a fact that is evidenced by this study on homomorphic evaluation of the AES circuit - https://eprint.iacr.org/2012/099.pdf. In summary, this paper demonstrates amortized time of 2 seconds for homomorphic evaluation of AES encryption per block at lattice dimension 46080 on a commodity laptop - the implementation leverages the so called "Gentry Halevi Smart optimizations" that are outlined here - https://eprint.iacr.org/2011/566. Halevi and Shoup's HElib provides a BGV backend with all of the features described above. Leo Ducas land Daniele Micciancio have another HE library available here https://github.com/lducas/FHEW, however I am not familiar with this scheme. I should also mention there is the multi key scheme by Lopez, Tromer and Vaikuntanathan based on the NTRU problem and a benchmark of homomorphic evaluation of AES based on this scheme over here - https://eprint.iacr.org/2014/039.pdf

Answer 2

The homomorphic encryption over the integers variants are much simpler to understand.

The idea is that your key is a random odd integer. to encrypt a bit, you add it (0 or 1) to the key multiplied by some integer (to hide the key better) and then add in a random even number to hide the key and value better.

To decrypt a bit, you mod by the key, then mod by two.

homomorphic AND and XOR is done by multiplying and adding encrypted bits, respectively.

One such paper: https://eprint.iacr.org/2009/616.pdf