In the context of fully homomorphic encryption, what is the difference between bootstrapping and recryption, since both offer the same result which is trying to eliminate/decrease the noise budget.
Description of bootstrapping:
In certain homomorphic encryption schemes, arithmetic oper-
ations on ciphertext can be performed using basic gates (AND, OR, NOT, etc)
but arbitrary operations could reduce the available noise budget. Bootstrapping
is a technique to remove noise by passing a ciphertext and encrypted private
key into a circuit that represents the decryption algorithm of a FHE scheme. This
results in a new ciphertext that corresponds to the original ciphertext but with
no noise. In the TFHE library, after every gate-by-gate operation, bootstrap-
ping is applied on the resultant ciphertext and hence any number of arbitrary
operations can be performed.
Description of Re-encryption:
Recryption is a technique to re-generate the noise budget of a ci-
phertext that was depleted by arbitrary computations. Recryption boosts bounded-
depth homomorphism to unbounded-depth homomorphism. This implies that
the noisy ciphertext can be converted into a noise-free ciphertext (of the same
plaintext) without the secret key. Libraries that do not have recryption
functionality implemented, provide no means of converting a noisy ciphertext to
a noise-free ciphertext. They therefore limit the number of arbitrary computa-
tions on a ciphertext.
