Since most of our asymmetric encryption algorithms are going to be out-of-date in a couple of year due to Shor's algorithm, I was wondering about the future of FHE schemes. I have found this paper, which states:

"It is impossible to construct secure group homomorphic encryption in the quantum world, if the plain-text and cipher-text spaces form abelian groups."

And I'm asking: are there any candidates which are also quantum resistant?

  • 4
    $\begingroup$ As the authors of the paper write of known FHE schemes: "Rather than having a group homomorphic decryption algorithm, the decryption is only guaranteed to run correctly for polynomially many evaluations of the group operation," and "The impact of our results on recent fully homomorphic encryption schemes poses itself as an open question." In other words, their generic attack does not work against known FHE schemes, which are indeed believed to be secure against quantum attacks. $\endgroup$ – Chris Peikert Aug 19 '15 at 21:29
  • $\begingroup$ @ChrisPeikert : $\:$ (I realize the paper does say that, but figure I should mention that) I thought all candidate schemes for depth beyond [c*log(n) for a constant c determined during key generation] are "guaranteed to run correctly for" arbitrarily "many evaluations of the group operation". $\;\;\;\;$ $\endgroup$ – user991 Aug 20 '15 at 8:31
  • $\begingroup$ For "bootstrapped" schemes, that's right. I haven't read this paper closely enough to see how existing FHEs fall outside their model of "group homomorphic" FHE, but according to the authors, they do somehow. $\endgroup$ – Chris Peikert Aug 20 '15 at 11:56

Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal lattices, BGV (based on ring-LWE), and this NTRU-based approach. All three are based on hard problems that are not susceptible to Shor's algorithm.


I do believe that none of the existent FHE is actually IND-CCA1 quantum resistant...the black-box group homomorphic proofs should work in the LWE world as well. The ring structure is hard to tackle in this setting, but I conjecture it will be done.


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.