11
$\begingroup$

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?

$\endgroup$
3
  • 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$ Aug 19, 2015 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, 2015 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$ Aug 20, 2015 at 11:56

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

There are quantum homomorphic encryption (QHE) schemes with information-theoretic security. While such QHE schemes do not perform arbitrary computations, and indeed, there are no-go results for fully QHE schemes. However, if one is willing to input sufficient resources, one can nonetheless have a sufficiently complex QHE scheme that has information-theoretic security.

Relevant QHE papers with information-theoretic security:

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

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