Why does bootstrapping (R)LWE homomorphic encryption produce small noise?

Question

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.

Answer 1

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.

Answer 2

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.