What is modulo switching, in a nutshell? Coupled with the terms bootstrapping and relinearization, the term modulo switching appears a lot in the FHE literature. What is it and how does it relate to the other two?
The basic idea:
In homomorphic encryption schemes, the ciphertexts are noisy and we want to refrain the noise from growing too fast as we operate homomorphically. So the idea here is to multiply a ciphertext $c$ defined over $\mathbb{Z}_{q_0}$ by $q_1 / q_0$ so that the noise term is also multiplied. Then, by setting $q_1 &lt; q_0$, we go from a noise term $e$ to a smaller noise approximately equal to $\frac{e q_1}{ q_0}$.
Furthermore, the ciphertext we obtain is then defined over $\mathbb{Z}_{q_1}$.
What is the advantage of doing this?
Let's say that fresh ciphertexts have noise term bounded by $B$ and that one homomorphic multiplication increases the noise to (approx.) $B^2$.
Then, two multiplications gives us $(B^2)^2 = B^{4}$, three gives us
$(B^4)^2 = B^8$... A sequence of $L$ multiplications increases the noise to $B^{2^L}$.
Because the final noise must be smaller than the modulus $q$, the bit length of $q$ must be bigger than $\log B^{2^L} = \Theta(2^L)$, that is, exponential in the circuit depth.
Now, imagine that we have $q_L := B^{L+1}$, $q_{L-1} := B^{L}$, $q_{L-2} := B^{L-1}$, ..., $q_{0} := B$. Then, $q_{i-1} / q_{i} = 1/B$.
Now, the first multiplication increases the noise close to $B^2$, but multiplying by $q_L / q_{L-1}$ scales it down to $B$ again.
Then, the second product increases the noise to $B^2$ and multiplying by $q_{L-1} / q_{L-2}$ (modulus switching) reduces the noise to $B$ again.
Proceeding like this, after $L$ multiplications, we have a ciphertext defined over $\mathbb Z_{q_0}$ with noise smaller than $B$, which can be correctly decrypted.
Now, the bit length of the modulus we need to use is $\log q_L = \Theta(L)$, that is, linear in the circuit depth instead of exponential!
But how the modulus switching is really done?
Of course, we can't simply multiply $c$ by $q_0 / q_1$, because we will not obtain a valid ciphertext, thus, each scheme has it is own way of getting a valid ciphertext out of $c\cdot q_0 / q_1$, but this is basically done by rounding.
For instance, let's say that we have the following LWE ciphertext with secret key $\vec s$ and noise term $e$:
$$
\vec c = (\vec a, \, \underbrace{\vec a\cdot \vec s + e + m \cdot q_0/2}_{b}) \in \mathbb{Z}_{q_0}^{n+1}.
$$
Then, over the integers, we have $b = \vec a\cdot \vec s + e + m \cdot q_0/2 + uq_0$
for some integer $u$.
Since the rounding function satisfies $\lceil x \rfloor = x + \epsilon$ with $-1/2 \le \epsilon \le 1/2$,
it is clear that
$$
b' := \lceil b \cdot q_1 / q_0 \rfloor 
= \vec a\cdot\vec s \cdot q_1 / q_0 + e \cdot q_1 / q_0 + m\cdot q_1 / 2 + \epsilon + uq_1 \in \mathbb{Z}.
$$
Using this trick again, we define
$\vec a' := \lceil \vec a \cdot q_1 / q_0 \rfloor = \vec a \cdot q_1 / q_0 + \vec \epsilon$, with rounding applied entry-wise, and obtain
$$
b'= \vec a' \vec s -\underbrace{ \vec \epsilon \vec s+ e \cdot q_1 / q_0 + \epsilon}_{e'} + m\cdot q_1 / 2 + uq_1 \in \mathbb{Z}.
$$
Finally, reducing $b'$ modulo $q_1$ removes the term $uq_1$.
Moreover, assuming that $||\vec s||$ is small, we see that the new noise $e'$ is close to original noise $e$ scaled by $q_1/q_0$.
Therefore,
$$\lceil \vec c \cdot q_1 / q_0 \rfloor \bmod q_1 = (\vec a', \, \vec a' \vec s + e' + mq_1/2) \in \mathbb{Z}_{q_1}^{n+1}$$
is a valid ciphertext of the same message, under the same key, but with smaller noise and with respect to a smaller modulus $q_1$.