Cryptography Asked by user991 on October 24, 2021
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.
and
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.)
According to the answer by Hilder Vitor Lima Pereira in the this question, the main scheme is believed to be quantum secure.
Answered by Robert Green on October 24, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP