5
$\begingroup$

I'm trying to understand the current context for fully homomorphic encryption. What are the most influential papers that are the basis for the most close-to-practical techniques today?

Of course Gentry's original paper is the most influential, but it is far from practical. A 2011 paper I see that appears to achieve much better performance (also by Gentry) is https://eprint.iacr.org/2011/277.pdf. What other papers published in the last 7 years are worth reading? (I would prefer papers with a post-quantum context in mind).

$\endgroup$
  • 1
    $\begingroup$ Are you talking about theoretical constructions or concrete implementations? $\endgroup$ – Florian Bourse Jun 15 '18 at 9:40
  • $\begingroup$ @FlorianBourse Both. But most papers on implementation are based on theoretical papers so theoretical constructions may be better to start. $\endgroup$ – Joseph Johnston Jun 15 '18 at 13:17
6
$\begingroup$

In short

BGV (the one you linked), FV and GSW.

More details

The scheme you have linked is known as BGV and I would say that it is the most important. There is a public implementation on Github. If the application can run in parallel, then BGV is probably the best current choice, because its plaintext space can be view as a product of rings, which gives the user the ability to encrypt several values in a single ciphertext. Then, a single homomorphic operation is actually equivalent to several plaintext operation in parallel.

The FV is another scheme with that feature and is the one that SEAL implements now.

If the application can't take advantage of the parallelism, then, I think the best choice nowadays is the so called FHE over the Torus, or TFHE.

Since you asked for influential papers, it is worth noting that TFHE is based on FHEW, by Miccianco, which is based on a paper by Sheriff Peikert, which is based on (this highly influential paper) GSW, again by Gentry.

Also, YASHE had an efficient version that was implemented by SEAL before, but it turned out to be insecure.

$\endgroup$
  • $\begingroup$ "If the application can't take advantage of the parallelism, then, I think the best choice nowadays is the so called FHE over the Torus, or TFHE." <-- Can you elaborate on this? $\endgroup$ – cygnusv Jun 15 '18 at 21:22
  • $\begingroup$ @cygnusv the cost of one homomophic operation plus refreshing the ciphertext (the bootstrapping) is much more expensive in BGV. As far as I know, TFHE has the best cost per homomorphic binary operation plus refreshing. However, one operation in BGV can act in parallel on several plaintexts if we pack them on a single ciphertext. Therefore, the total cost to perfom some task homomorphically can still be smaller using BGV if we are able to exploit all that parallelism. $\endgroup$ – Hilder Vítor Lima Pereira Jun 16 '18 at 7:16
  • $\begingroup$ @cygnusv This is what authors claim, for instance, in minute 33 of this presentation in ASIACRYPT: youtu.be/A-z4kWfSwQk?t=33m $\endgroup$ – Hilder Vítor Lima Pereira Jun 16 '18 at 7:21
  • $\begingroup$ @HilderVitorLimaPereira Thank you. Can you point to the FV paper? $\endgroup$ – Joseph Johnston Jun 16 '18 at 9:18
  • 1
    $\begingroup$ In addition to the ones mentioned I'd suggest adding the CKKS (Cheon-Kim-Kim-Song) scheme. It allows homomorphic calculations on real and complex numbers, but only yields approximate results. It's your best choice if you try to e.g. train a neuronal network with encrypted data. It's also implemented in Microsofts SEAL (in addition to (B)FV). $\endgroup$ – kappadoky Aug 11 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.