I was reading the paper Fully Homomorphic Encryption over the Integers, and started
wondering if there is a known quantum attack on their main scheme, because

There is an efficient quantum attack on their "even slightly simpler scheme", as follows:
completely factor $x_{\hspace{.025 in}0}$,
for each [product of a very small number of $\hspace{.03 in}x_{\hspace{.025 in}0}\hspace{-0.04 in}$'s prime factors] with the right number of bits,
see if using that as a private key correctly decrypts a moderate
number of "test ciphertexts" generated for that purpose
if one does, then use it to decrypt the challenge ciphertext and output that decryption result
otherwise output failure

That attack works because $p$, as a random odd integer of a given bit length, has a noticeable
probability of being prime, so in particular of having a very small number of prime factors.


The section that describes their "even slightly simpler scheme" also says they
"do not know of ant attack that works for this 'easier case' but not for the general case.".
(The "ant" typo is in the paper that I linked to.)

On the other hand, the version on Springer does not include that section.

Is there a known efficient quantum attack on the main scheme of those two papers?

(I say "those two papers" because I'm not aware of any difference between their schemes,
and if there is one then I don't know which of them I mean.)

  • $\begingroup$ But they do not claim that their scheme is post-quantum right? $\endgroup$ – DrLecter May 9 '14 at 18:20
  • 1
    $\begingroup$ Right, they do not claim that their scheme is post-quantum. $\;$ $\endgroup$ – user991 May 9 '14 at 19:10
  • $\begingroup$ If there's any attack that is reducible to HSP for finite Abelian groups or groups 'close enough' to Abelian (quaternions for example) its insecure against quantum computing attacks. The ciphertext compression is trivially reducible to the Abelian HSP, but the actual encryption scheme isn't obviously so. $\endgroup$ – dezakin Jun 11 '14 at 0:57

According to the answer by Hilder Vitor Lima Pereira in the this question, the main scheme is believed to be quantum secure.

| improve this answer | |

Your Answer

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