Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)

share|improve this question
But they do not claim that their scheme is post-quantum right? – DrLecter May 9 '14 at 18:20
Right, they do not claim that their scheme is post-quantum. $\;$ – Ricky Demer May 9 '14 at 19:10
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. – dezakin Jun 11 '14 at 0:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.