2
$\begingroup$

Why does homomorphic evaluation of the decryption circuit produce a ciphertext with "fresh" or small noise?

Rough description of bootstrapping homomorphic encryption:

Suppose we have a somewhat homomorphic encryption scheme that can only evaluate circuits of small depths including its own decryption circuit. In (R)LWE schemes, this is due to the growth of the noise in the ciphertext produced by homormorphic evaluation, which eventually makes the resulting ciphertext undecryptable.

Bootstrapping is the procedure that homomorphically evaluates the decryption of the current ciphertext, which produces a new ciphertext encrypting the same message. Supposedly, the new ciphertext should have smaller noise, which allows for further homomorphic evaluation.

I understand that bootstrapping produces a new ciphertext of the same message. But why does it have any smaller noise? It's still just evaluation of a circuit, which in general, increases the noise.

$\endgroup$
1
  • $\begingroup$ Isn't clear, but sometimes hard to understand. Consider that you decrypt the ciphertext then the noise can be eliminated, right? Now consider that you executed this homomorphically, and the resulting plaintext again encrypted.\ $\endgroup$
    – kelalaka
    Mar 29, 2021 at 22:17

2 Answers 2

4
$\begingroup$

The output of bootstrapping has relatively small noise because it starts from an encryption (of the secret key) that has very small noise, and performs some homomorphic operations on it. These operations increase the noise somewhat, but it starts out so small that the result still doesn’t have much noise.

It doesn’t really matter that the ciphertext being bootstrapped has large noise, because that ciphertext only defines the function we (homomorphically) evaluate, namely, decryption of that fixed ciphertext by the (encrypted) secret key. In other words, the secret key is the input to the function we homomorphically evaluate, and it is encrypted with very small noise, so the result has only moderate noise.

$\endgroup$
2
$\begingroup$

It's still just evaluation of a circuit, which in general, increases the noise.

Yes and no. Homomorphic operations do (generically) increase the noise, but the idea behind bootstrapping is to evaluate a circuit which itself decrypts the ciphertext. Decrypting the ciphertext (if the noise is below some threshold) zeros out the noise. This means there are two "competing" ways the noise is impacted by bootstrapping:

  1. The homomorphic operations themselves increase the noise, as you say

  2. The bootstrapping circuit (if computed in the clear) zeros out the noise

Give the above, it should be plausible one could balance the amount the noise increases/shrinks to end up with (net) less noise. This is precisely what bootstrapping does.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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