8
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ See The second technique is modulus switching $\endgroup$ – kelalaka Dec 30 '18 at 23:09
  • $\begingroup$ @kelalaka So, in a nutshell: relinearization is modulo-switching. Is that correct? Two names for the very same thing? $\endgroup$ – Daniel Dec 30 '18 at 23:10
  • $\begingroup$ AFAIK, no see 3.3 $\endgroup$ – kelalaka Dec 30 '18 at 23:15
  • $\begingroup$ @kelalaka Thanks for the references. I will take a look. $\endgroup$ – Daniel Dec 30 '18 at 23:18
  • 1
    $\begingroup$ 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. $\endgroup$ – LeoDucas Jan 2 '19 at 6:29
6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

He has already answered the rest of your question about bootstrapping and relinearization here on crypto.stackexchange.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the answer! $\endgroup$ – Daniel Feb 3 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.