2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the quick and detailed response! $\endgroup$
    – Freak14
    Aug 9, 2023 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.