6
$\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).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Are you talking about theoretical constructions or concrete implementations? $\endgroup$
    – Florian Bourse
    Jun 15, 2018 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, 2018 at 13:17

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
6
  • $\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, 2018 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 Vitor Lima Pereira
    Jun 16, 2018 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 Vitor Lima Pereira
    Jun 16, 2018 at 7:21
  • $\begingroup$ @HilderVitorLimaPereira Thank you. Can you point to the FV paper? $\endgroup$
    – Joseph Johnston
    Jun 16, 2018 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, 2019 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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