# FHE Bootstrapping vs. Relinearization

In the context of Fully Homomorphic Encryption, what is the difference between Bootstrapping and Relinearization? Between two of them, which is the more expensive (computationally) and why?

• I think Relin method is applied to (R)LWE-based (only) schemes and bootstrapping is more general. Can be applied in any SHE scheme. – 111 Mar 13 '17 at 16:23

2. reduce the ciphertext's size after multiplication (for instance, in this scheme, the ciphertext's size grows from $n$ to $n^2$ elements after multiplication and relinearization is used to generate ciphertexts again with $n$ elements);
3. make a ciphertext decryptable under the original secret key: in some (RLWE based) schemes, when we multiply two ciphertexts encrypted under a secret key $s$, we obtain a ciphertext encrypted under $s^2$. Then, relinearization (which is usually called keySwitch in those works) is used to obtain a new ciphertext that encrypts the same product but under $s$. (See, for instance, this work).