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

• Dec 30, 2018 at 23:09
• @kelalaka So, in a nutshell: relinearization is modulo-switching. Is that correct? Two names for the very same thing? Dec 30, 2018 at 23:10
• AFAIK, no see 3.3 Dec 30, 2018 at 23:15
• @kelalaka Thanks for the references. I will take a look. Dec 30, 2018 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. Jan 2, 2019 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$$.

• I still don't understand how this is useful. The noise does decrease, but the relative noise is about the same (or increases); i.e. $|e|/q_0\approx |e'|/q_1$. The smaller modulus tolerates less noise, so it doesn't seem that there's any gain. My intuition must be wrong, but I can't see my misunderstanding.
– yoyo
Mar 9 at 22:09
• The relative noises are basically the same, that is true. But as I explained in the answer, at the end, you can choose $\log q_L = \Theta(L)$. One explanation for the gain is that if you just multiply ciphertexts, you are "combining" the noises, so the noise grows exponentially fast. But when you switch the modulus, both ciphertexts work mod the new q_i without "combining" the moduli, so the (log of the) modulus decreases linearly instead of exponentially. That is where you gain something. Mar 10 at 8:16
• Thanks for your response. As used in Efficient Fully Homomorphic Encryption from (Standard) LWE, modulus-dimension reduction isn't really a "noise reduction" technique, but rather decreases the complexity of decryption to allow bootstrapping. As you describe modulus switching, it keeps the modulus (much) smaller than naively expected for a given multiplicative depth. In either case, I think I now understand its utility.
– yoyo
Mar 10 at 18:32

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..."