Score:2

Is it possible to perform an unlimited amount of multiplications on the same ciphertext in fully homomorphic encryption?

bt flag

I am currently playing around with some of the Python FHE libraries and found out that, e.g. TenSeal (SEAL) is able to perform "only" 8 ciphertext-ciphertext multiplications on the same ciphertext (8x1 Vector) (c1 = c1*c2 in a loop) before the noise threshold is surpassed and decryption fails.

The parameters I set for this are: poly_modulus_degree=16384 and plain_modulus=536903681 using the BFV Scheme.

Is it even possible to perform arbitrary amounts of operations on the same ciphertext, assuming runtime is irrelevant? I understand, that multiplication operations increase noise significantly, but methods like bootstrapping and relinearization do not seem to decrease the noise in a way, that would allow an unlimited amount of computations, right?

Score:2
cn flag

Yes, a bootstrappable homomorphic encryption scheme can allow arbitrarily many multiplications. Using bootstrapping (i.e. running the decryption circuit homomorphically), we can refresh the noise on a ciphertext. Running bootstrapping itself adds noise, but as long as you are able to perform the decryption circuit along with another multiplication, you can perform arbitrarily long circuits. For more information, see this answer on another SE question, this Wikipedia entry and Craig Gentry's paper.

Freak14 avatar
bt flag
Thanks for the quick and detailed response!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.