# 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?

• – kelalaka Dec 30 '18 at 23:09
• @kelalaka So, in a nutshell: relinearization is modulo-switching. Is that correct? Two names for the very same thing? – Daniel Dec 30 '18 at 23:10
• AFAIK, no see 3.3 – kelalaka Dec 30 '18 at 23:15
• @kelalaka Thanks for the references. I will take a look. – Daniel Dec 30 '18 at 23:18
• Modulus switching can be viewed as dropping precision (thinking of the group $\mathbb Z/q\mathbb Z$ as a scaled discretization of the torus $\mathbb R/\mathbb Z$). Basically dropping integral'' ticks on the continuous circle. – LeoDucas Jan 2 '19 at 6:29

## 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 < 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$$.

Hilder Vitor Lima Pereira described modulo switching in a paper entitled Bootstrapping fully homomorphic encryption over the integers in less than one second as "a method to reduce the noise by scaling a ciphertext and switching the modulus of the ciphertext space..."