Why does bootstrapping (R)LWE homomorphic encryption produce small noise? Why does homomorphic evaluation of the decryption circuit produce a ciphertext with &quot;fresh&quot; 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.
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.