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?
Bootstrapping is the procedure that refreshs a ciphertext by running the decryption function homomorphically. By refresh you should think in something like decrypting and encrypting again, so the resulting ciphertext has little noise on it. Therefore, the main goal of bootstrapping is to manage the noise and it is used to transform a somewhat homomorphic encryption scheme into a fully homomorphic one.
Relinearization is a technique to transform quadratic equations in linear ones (generally, on a different set of variables). It is used to
- gain the ability of performing homomorphic multiplications over (algebraic) structures that would allow only homomorphic additions;
- 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);
- 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).
which is the more expensive (computationally) and why?
I think that it depends on the scheme, but, in general, bootstrapping is more expensive because it involves evaluating the decryption circuit homomorphically while relinearization is usually performed just by calculating a inner product. Furthermore, bootstrapping almost always requires squashing the decryption circuit so that it can be evaluated homomorphically, but such changes on the scheme generate a more complex scheme with bigger ciphertexts and keys (which makes everything more expensive).