D-4.7 Modulus Switch

- Reference 1: Design and implementation of HElib: a homomorphic encryption library [21]

- Reference 2: Fully Homomorphic Encryption without Bootstrapping [22]

- Reference 3: Homomorphic Evaluation of the AES Circuit [23]

Remember that the requirement of modulus switch is that while we change the ciphertext modulus from $q$ to $\widehat{q}$, it should decrypt to the same plaintext $M$. BGV’s modulus switch is similar to that of the RLWE modulus switch (§C-4.4), but there is an additional requirement, because BGV applies the scaling factor $\mathrm{\Delta }$ not to plaintext $M$, but to noise $E$. In the case of BFV or CKKS, their decryption process only needs to round off the noise in the low-digit area. However, in the case of BGV, the plaintext is in the low-digit area and its decryption process has to remove the noise in the higher-bit area by modulo-$t$ reduction (i.e., the plaintext modulus). More concretely, BGV’s modulus switch from $(A,B)mod{q}_l$ $\to$ $(\widehat{A},\widehat{B})mod\widehat{q}$ should satisfy the decryption relation such that $((\widehat{A}\cdot S+\widehat{B})mod\widehat{q})modt=M$. In BGV’s modulus switch, $\widehat{q}$ does not have to be one of the multiplicative levels of the ciphertext, and $\widehat{q}$ only needs to satisfy the relationship: $\widehat{q}<q_l$ and $\widehat{q}\equiv 1modt$. BGV’s modulus switch procedure is as follows:

1.

The input ciphertext is $\mathsf{\text{𝖼𝗍}}=(A,B)mod{q}_l$. We compute new polynomials $A^{\prime }$ and $B^{\prime }$ as follows:

$(A^{\prime },B^{\prime })=\left(\lceil {\displaystyle \frac{\widehat{q}}{q_l}}\cdot A\rfloor ,\lceil {\displaystyle \frac{\widehat{q}}{q_l}}\cdot B\rfloor \right)(\mathit{𝑚𝑜𝑑}\widehat{q})$

$$

And we compute the rounding error ${𝜖}_A,{𝜖}_B$ as follows:

${𝜖}_A={\displaystyle \frac{\widehat{q}}{q_l}}\cdot A-A^{\prime }$

${𝜖}_B={\displaystyle \frac{\widehat{q}}{q_l}}\cdot B-B^{\prime }$

$$

, which we rewrite as follows:

$\widehat{q}A=q_l{A}^{\prime }+q_l{𝜖}_A=q_l{A}^{\prime }+{𝜖}_A^{\prime }$ # we denote ${𝜖}_A^{\prime }=q_l{𝜖}_A$, where ${𝜖}_A^{\prime }\in {\mathbb{Z}}_{q_l}$

$\widehat{q}B=q_l{B}^{\prime }+q_l{𝜖}_B=q_l{B}^{\prime }+{𝜖}_B^{\prime }$ # we denote ${𝜖}_B^{\prime }=q_l{𝜖}_B$, where ${𝜖}_B^{\prime }\in {\mathbb{Z}}_{q_l}$

$$

2.

We compute new polynomials $H_A$ and $H_B$ as follows:

$H_A=q_l^{-1}\cdot {𝜖}_A^{\prime }modt$

$H_B=q_l^{-1}\cdot {𝜖}_B^{\prime }modt$

$$

3.

We compute the final mod-switched ciphertext $\widehat{\mathsf{\text{𝖼𝗍}}}$ as follows:

$\widehat{\mathsf{\text{𝖼𝗍}}}=(\widehat{A},\widehat{B})=(A^{\prime }+H_A,B^{\prime }+H_B)mod\widehat{q}$

$$

Note that the computation result of $A^{\prime }+H_A$ and $B^{\prime }+H_B$ alone can exceed the range ${\mathbb{Z}}_{\widehat{q}}$, because $A^{\prime },B^{\prime }\in {\mathbb{Z}}_{\widehat{q}}$ and $H_A,H_B\in {\mathbb{Z}}_t$. Therefore, we need to reduce $A^{\prime }+H_A$ and $B^{\prime }+H_B$ modulo $\widehat{q}$ to derive $\widehat{A}\in {\mathbb{Z}}_{\widehat{q}}$ and $\widehat{B}\in {\mathbb{Z}}_{\widehat{q}}$.

$$

4.

From now on, we will verify that $\widehat{\mathsf{\text{𝖼𝗍}}}$ is a valid ciphertext satisfying BGV’s required decryption relation. First, we can derive the relationship among $\mathsf{\text{𝖼𝗍}}=(A,B)$, $A^{\prime }+H_A$, and $B^{\prime }+H_B$ as follows:

$\widehat{q}\cdot \mathsf{\text{𝖼𝗍}}modt=(\widehat{q}A,\widehat{q}B)modt$

$=(q_l{A}^{\prime }+{𝜖}_A^{\prime },q_l{B}^{\prime }+{𝜖}_B^{\prime })modt$ # applying step 1’s result: $\widehat{q}A=q_l{A}^{\prime }+{𝜖}_A^{\prime }$, $\widehat{q}B=q_l{B}^{\prime }+{𝜖}_B^{\prime }$

$=(q_l{A}^{\prime }+q_l{H}_A,q_l{B}^{\prime }+q_l{H}_B)modt$ # applying step 2’s result: $H_A=q_l^{-1}\cdot {𝜖}_A^{\prime }modt$, $H_B=q_l^{-1}\cdot {𝜖}_B^{\prime }modt$

$$

$=q_l\cdot (A^{\prime }+H_A,B^{\prime }+H_B)modt$

$$

So, $\widehat{q}\cdot \mathsf{\text{𝖼𝗍}}=q_l\cdot (A^{\prime }+H_A,B^{\prime }+H_B)modt$. But in BGV, $q_l\equiv q_2\equiv \cdots q_L\equiv 1modt$. Thus, the following holds:

$\mathsf{\text{𝖼𝗍}}=(A,B)=(A^{\prime }+H_A,B^{\prime }+H_B)(\mathit{𝑚𝑜𝑑}t)$

$$

5.

We can derive the decryption relation of $\widehat{\mathsf{\text{𝖼𝗍}}}$ from the decryption relation of $\mathsf{\text{𝖼𝗍}}$ as follows:

$M=(A\cdot S+Bmod{q}_l)modt$ # The BGV decryption relation of $\mathsf{\text{𝖼𝗍}}=(A,B)mod{q}_l$

$=(A\cdot S+B-K\cdot q_l)modt$ # where $K\cdot q_l$ represents the modulo-$q_l$ reduction

$=((A^{\prime }+H_A)\cdot S+B^{\prime }+H_B-K\cdot q_l)modt$ # applying step 4’s result: $A\equiv A^{\prime }+H_{A}modt$, $B\equiv B^{\prime }+H_{B}modt$

$=((A^{\prime }+H_A)\cdot S+B^{\prime }+H_B-K\cdot \widehat{q})modt$ # since in BGV, $q_1\equiv q_2\equiv \cdots q_L\equiv 1modt$, and we chose $\widehat{q}$ such that $\widehat{q}\equiv 1modt$

$$

Now, if we can prove that $(A^{\prime }+H_A)\cdot S+B^{\prime }+H_B-K\cdot \widehat{q}=(A^{\prime }+H_A)\cdot S+B^{\prime }+H_{B}mod\widehat{q}$ (i.e., $K\cdot \widehat{q}$ reduces $(A^{\prime }+H_A)\cdot S+B^{\prime }+H_B$ modulo-$\widehat{q}$), then this sufficiently leads to the conclusion that $((A^{\prime }+H_A)\cdot S+B^{\prime }+H_{B}mod\widehat{q})modt=M$.

$$

6.

The following is also true:

$(A^{\prime }+H_A)\cdot S+B^{\prime }+H_{B}mod\widehat{q}$

$=|A^{\prime }+H_A{|}_{\widehat{q}}\cdot S+|B^{\prime }+H_B{|}_{\widehat{q}}mod\widehat{q}$

# where $|A^{\prime }+H_A{|}_{\widehat{q}}=A^{\prime }+H_{A}mod\widehat{q}$, $|B^{\prime }+H_B{|}_{\widehat{q}}=B^{\prime }+H_{B}mod\widehat{q}$

$$

$=\widehat{A}\cdot S+\widehat{B}mod\widehat{q}$ # applying step 3: $\widehat{A}=A^{\prime }+H_{A}mod\widehat{q}$, $\widehat{B}=B^{\prime }+H_{B}mod\widehat{q}$

$$

Therefore, proving $(A^{\prime }+H_A)\cdot S+B^{\prime }+H_B-K\cdot \widehat{q}=(A^{\prime }+H_A)\cdot S+B^{\prime }+H_{B}mod\widehat{q}$ is equivalent to proving $(A^{\prime }+H_A)\cdot S+B^{\prime }+H_B-K\cdot \widehat{q}=\widehat{A}\cdot S+\widehat{B}mod\widehat{q}$.

$$

7.

We will prove that $(A^{\prime }+H_A)\cdot S+B^{\prime }+H_B-K\cdot \widehat{q}=(A^{\prime }+H_A)\cdot S+B^{\prime }+H_{B}mod\widehat{q}$ as follows:

$(A^{\prime }+H_A)\cdot S+B^{\prime }+H_B-K\cdot \widehat{q}$

$=({\displaystyle \frac{\widehat{q}}{q_l}}\cdot A-{\displaystyle \frac{{𝜖}_A^{\prime }}{q_l}}+H_A)\cdot S+({\displaystyle \frac{\widehat{q}}{q_l}}\cdot B-{\displaystyle \frac{{𝜖}_B^{\prime }}{q_l}}+H_B)-K\cdot \widehat{q}$

# applying step 1’s result: $A^{\prime }={\displaystyle \frac{\widehat{q}}{q_l}}\cdot A-{\displaystyle \frac{{𝜖}_A^{\prime }}{q_l}},B^{\prime }={\displaystyle \frac{\widehat{q}}{q_l}}\cdot B-{\displaystyle \frac{{𝜖}_B^{\prime }}{q_l}}$

$$

$$

$=\left({\displaystyle \frac{\widehat{q}}{q_l}}\cdot A\cdot S+{\displaystyle \frac{\widehat{q}}{q_l}}\cdot B-K\cdot \widehat{q}\right)+H_A\cdot S+H_B-{\displaystyle \frac{{𝜖}_A^{\prime }}{q_l}}\cdot S-{\displaystyle \frac{{𝜖}_B^{\prime }}{q_l}}$ # rearranging the terms

$={\displaystyle \frac{\widehat{q}}{q_l}}\cdot (A\cdot S+B-K\cdot q_l)+H_A\cdot S+H_B-{\displaystyle \frac{{𝜖}_A^{\prime }}{q_l}}\cdot S-{\displaystyle \frac{{𝜖}_B^{\prime }}{q_l}}$ # taking out the common factor ${\displaystyle \frac{\widehat{q}}{q_l}}$

$={\displaystyle \frac{\widehat{q}}{q_l}}\cdot (A\cdot S+Bmod{q}_l)+H_A\cdot S+H_B-{\displaystyle \frac{{𝜖}_A^{\prime }\cdot S+{𝜖}_B^{\prime }}{q_l}}$ # since $A\cdot S+B-K\cdot q_l=A\cdot S+Bmod{q}_l$

$$

For successful decryption, every coefficient of the resulting polynomial of the above expression has to be within the range ${\mathbb{Z}}_{\widehat{q}}$ (which means that $K\cdot \widehat{q}$ has successfully reduced $(A^{\prime }+H_A)\cdot S+B^{\prime }+H_B$ modulo $\widehat{q}$). The first term ${\displaystyle \frac{\widehat{q}}{q_l}}\cdot (A\cdot S+Bmod{q}_l)$ can be viewed as the original ciphertext ct’s noise (with the plaintext message) scaled down by ${\displaystyle \frac{\widehat{q}}{q_l}}$. The coefficients of the second term $H_A\cdot S$ are also small, because $H_A\in {\mathbb{Z}}_t$ and $S\in {\mathbb{Z}}_3$. The coefficients of the third term $H_B$ are also small, because $H_B\in {\mathbb{Z}}_t$. The coefficients of the last term $-{\displaystyle \frac{{𝜖}_A^{\prime }\cdot S+{𝜖}_B^{\prime }}{q_l}}$ are also small, because ${\displaystyle \frac{{𝜖}_A^{\prime }}{q_l}}$ and ${\displaystyle \frac{{𝜖}_B^{\prime }}{q_l}}$ are $\in {\mathbb{Z}}_{\frac{q_l}{\widehat{q}}}$.

$$

Therefore, $(A^{\prime }+H_A)\cdot S+B^{\prime }+H_B-K\cdot \widehat{q}=(A^{\prime }+H_A)\cdot S+B^{\prime }+H_{B}mod\widehat{q}$ (provided the above error thresholds hold).

$$

8.

Finally, we combine the results of step 6 and 7 as follows:

$(\widehat{A}\cdot S+\widehat{B})mod\widehat{q}modt$

$=((A^{\prime }+H_A)\cdot S+B^{\prime }+H_{B}mod\widehat{q})modt$ # by applying step 6

$=(A\cdot S+Bmod{q}_l)modt$ # by applying step 7

$=M$

$$

This means that decrypting $(\widehat{A},\widehat{B})mod\widehat{q}$ outputs the message $M$.

We summarize BGV’s modulus switch as follows:

D-4.7.1 Difference between Modulus Switch and ModDrop

In the case of CKKS (§D-3.5.4), the difference between modulus switch and ModDrop is that the former scales down the plaintext’s scaling factor by ${\displaystyle \frac{q_l}{q_{l-1}}}\approx {\displaystyle \frac{1}{\mathrm{\Delta }}}$, whereas ModDrop does not affect the plaintext’s scaling factor.

Similarly, in the case of BGV, modulus switch (rescaling) and ModDrop from $q_l\to q_{l-1}$ both lower a BGV ciphertext’s modulus from $q_l\to q_{l-1}$. However, the key difference is that rescaling also decreases the noise’s scaling factor by ${\displaystyle \frac{q_l}{q_{l-1}}}\approx {\displaystyle \frac{1}{\mathrm{\Delta }}}$, whereas ModDrop keeps the noise’s scaling factor the same as it is. Therefore, rescaling is used only during ciphertext-to-ciphertext multiplication (to be explained in §D-4.8) when scaling down the plaintext’s scaling factor in the intermediate ciphertext from ${\mathrm{\Delta }}^2\to \mathrm{\Delta }$. Meanwhile, ModDrop is used to reduce the modulo computation time during an application’s routine when it becomes certain that the ciphertext will not undergo any additional ciphertext-to-ciphertext multiplication (i.e., no need to further decrease the ciphertext’s modulus).

The main difference in modulus switch between CKKS and BGV is that the former decreases the plaintext’s scaling factor by approximately ${\displaystyle \frac{1}{\mathrm{\Delta }}}$, whereas the latter decreases the noise’s scaling factor by approximately ${\displaystyle \frac{1}{\mathrm{\Delta }}}$.

Source Code: Examples of BGV modulus switch can be executed by running this Python script.