TransWikia.com

FHE over the integers - Is that paper's scheme known to be insecure against quantum adversaries?

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

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP