D-5.5 RNS-based Modulus Switch: ModSwitch_RNS

Modulus switch is an operation of reducing a ciphertext’s modulus from $q$ to $q^{\prime }$ (where $q^{\prime }<q$) and updating the target value from $x$ to $\lceil x\cdot {\displaystyle \frac{q^{\prime }}{q}}\rfloor$. Modulus switch is used for lowering the multiplicative level of a ciphertext upon each ciphertext-to-ciphertext multiplication (in the case of BFV, CKKS, or BGV) or even upon each ciphertext-to-plaintext multiplication (in the case of CKKS). Upon each modulus switch from $q\to q^{\prime }$ of a ciphertext, the scaling factor of the underlying plaintext in the ciphertext also gets reduced by the same proportion: ${\displaystyle \frac{q^{\prime }}{q}}$.

The modulus switch operation of an RNS-based ciphertext is denoted as ModSwitch_RNS, which requires that the output base moduli are a subset of the input base moduli. In other words, like the case of ModDrop_RNS, it only supports a modulus switch from $\mathit{𝑞𝑏}\to q$, where $q$ and $b$ are co-prime.

Suppose we have $({\chi }_1,{\chi }_2,\cdots ,{\chi }_{k+l})\in {\mathbb{Z}}_{q_1}\times {\mathbb{Z}}_{q_2}\times \cdots \times {\mathbb{Z}}_{q_k}\times {\mathbb{Z}}_{b_1}\times {\mathbb{Z}}_{b_2}\times \cdots \times {\mathbb{Z}}_{b_l}$, which represents the value $\chi =\left(\underset{i=1}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\left|{\chi }_i\cdot {\left({\displaystyle \frac{\mathit{𝑞𝑏}}{q_i}}\right)}^{-1}\right|}_{q_i}\cdot {\displaystyle \frac{\mathit{𝑞𝑏}}{q_i}}\right)+\left(\underset{j=k+1}{\overset{k+l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\left|{\chi }_j\cdot {\left({\displaystyle \frac{\mathit{𝑞𝑏}}{b_j}}\right)}^{-1}\right|}_{b_j}\cdot {\displaystyle \frac{\mathit{𝑞𝑏}}{b_j}}\right)mod\mathit{𝑞𝑏}$.

Given $\chi \in {\mathbb{Z}}_{\mathit{𝑞𝑏}}$, ModSwitch_RNS from $\mathit{𝑞𝑏}\to q$ is an operation of updating $\chi \in {\mathbb{Z}}_{\mathit{𝑞𝑏}}$ to some $y\in {\mathbb{Z}}_q$ where $y\approx \lceil {\displaystyle \frac{\chi }{b}}\rfloor$. Unlike in regular modulus switch where we can directly arithmetically divide $\chi$ by $b$ and round it, an RNS vector is incompatible with direct arithmetic division on the residues. Therefore, our alternative strategy is to find some small value $\widehat{\chi }$ such that $\chi \equiv \widehat{\chi }modb$. Once we find such $\widehat{\chi }$, then $\chi -\widehat{\chi }mod\mathit{𝑞𝑏}$ becomes divisible by $b$ (since their difference is some multiple of $b$), and thus we can compute ${\displaystyle \frac{\chi -\widehat{\chi }}{b}}\approx \lceil {\displaystyle \frac{\chi }{b}}\rfloor$. Note that in this computation, the additionally introduced error of modulus switch caused by replacing $\chi$ with $\chi -\widehat{\chi }$ is equivalent to: $|\lceil {\displaystyle \frac{\chi }{b}}\rfloor -{\displaystyle \frac{\chi -\widehat{\chi }}{b}}|\approx \lceil {\displaystyle \frac{\widehat{\chi }}{b}}\rfloor$. After the (exact) division of ${\displaystyle \frac{\chi -\widehat{\chi }}{b}}$, we directly replace the modulus $\mathit{𝑞𝑏}$ with $q$. This direct replacement of modulus is arithmetically allowed because the computation result of ${\displaystyle \frac{\chi -\widehat{\chi }}{b}}$ is guaranteed to be within $-{\displaystyle \frac{q}{2}}$ and ${\displaystyle \frac{q}{2}}-1$ (since $-{\displaystyle \frac{\mathit{𝑞𝑏}}{2}}\le \chi \le {\displaystyle \frac{\mathit{𝑞𝑏}}{2}}-1$). Therefore, we can derive the following formula:

${\displaystyle \frac{\chi -\widehat{\chi }}{b}}modq=|b^{-1}{|}_q\cdot (\chi -\widehat{\chi })modq$

In the above relation, we can arithmetically replace $b$ with $|b^{-1}{|}_q$, because $\chi -\widehat{\chi }$ is divisible by $b$ and $b$ is guaranteed to have an inverse modulo $q$ (since $b$ and $q$ are co-prime). Next, we can compute $|b^{-1}{|}_q\cdot (\chi -\widehat{\chi })modq$ based on their RNS residues as follows:

$|b^{-1}{|}_q\cdot (\chi -\widehat{\chi })modq$

$=(|b^{-1}{|}_{q_1}\cdot ({\chi }_1-{\widehat{\chi }}_1),|b^{-1}{|}_{q_2}\cdot ({\chi }_2-{\widehat{\chi }}_2),\cdots ,|b^{-1}{|}_{q_k}\cdot ({\chi }_k-{\widehat{\chi }}_k))\in {\mathbb{Z}}_{q_1}\times {\mathbb{Z}}_{q_2}\times \cdots \times {\mathbb{Z}}_{q_k}$

$=(y_1,y_2,\cdots ,y_k)$ $▹$ where each $y_i=|b^{-1}{|}_{q_i}\cdot ({\chi }_i-{\widehat{\chi }}_i)mod{q}_i$

Now, our task is to derive an expression for some small $\widehat{\chi }$ such that $\chi -\widehat{\chi }$ is divisible by $b$. We propose that $\widehat{\chi }=|\chi {|}_b+\mathit{𝑢𝑏}$ for some small integer $|u|\le {\displaystyle \frac{l}{2}}+1$. Then, notice that $\chi -\widehat{\chi }$ is divisible by $b$ as follows:

$|\chi -\widehat{\chi }{|}_b=||\chi {|}_b-(|\chi {|}_b+\mathit{𝑢𝑏}){|}_b=|-\mathit{𝑢𝑏}{|}_b=0$

Now, we will derive the RNS vector of $\widehat{\chi }modq=|\chi {|}_b+\mathit{𝑢𝑏}modq$, which is to be plugged into $|b^{-1}{|}_q\cdot (\chi -\widehat{\chi })modq$. First, we derive the RNS vector of $|\chi {|}_b$ as follows:

$(|\chi {|}_{b_1},|\chi {|}_{b_2},\cdots ,|\chi {|}_{b_l})=({\chi }_{k+1},{\chi }_{k+2},\cdots ,{\chi }_{k+l})\in {\mathbb{Z}}_{b_1}\times {\mathbb{Z}}_{b_2}\times \cdots \times {\mathbb{Z}}_{b_l}$

Next, we can compute its fast base conversion from $b\to q$ as follows:

$\mathsf{\text{𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏}}({\{{\chi }_{k+i}\}}_{i=1}^l,b,q)$

$=({\widehat{\chi }}_1,{\widehat{\chi }}_2,\cdots ,{\widehat{\chi }}_k)\in {\mathbb{Z}}_{q_1}\times {\mathbb{Z}}_{q_2}\times \cdots \times {\mathbb{Z}}_{q_k}$

Now, notice that the above RNS residue vector $({\widehat{\chi }}_1,{\widehat{\chi }}_2,\cdots ,{\widehat{\chi }}_k)$ represents the value $\widehat{\chi }=|\chi {|}_b+u\cdot bmodq$ (where integer $|u|\le {\displaystyle \frac{l}{2}}+1$), which is our desired formula for $\widehat{\chi }$. Therefore, $\widehat{\chi }=\mathsf{\text{𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏}}({\{{\chi }_{k+i}\}}_{i=1}^l,b,q)$.

Note that $\widehat{\chi }\ll {\displaystyle \frac{q}{2}}-1$ and $-{\displaystyle \frac{q}{2}}\ll \widehat{\chi }$, because $||\chi {|}_b+u\cdot b|<\left({\displaystyle \frac{l}{2}}+1\right)\cdot b+{\displaystyle \frac{b}{2}}\ll {\displaystyle \frac{q}{2}}$ (here we assume that $b\ll q$, as we assume the modulus switch operation is used to remove only a single prime factor from the large base $q$). Therefore, the magnitude of the error generated by computing $b^{-1}\cdot (\chi -\widehat{\chi })$ is approximately $\lceil {\displaystyle \frac{\widehat{\chi }}{b}}\rfloor <\lceil {\displaystyle \frac{\left({\displaystyle \frac{l}{2}}+1\right)\cdot b+{\displaystyle \frac{b}{2}}}{b}}\rfloor =\lceil {\displaystyle \frac{\mathit{𝑙𝑏}+3b}{2b}}\rfloor =\lceil {\displaystyle \frac{l+3}{2}}\rfloor <{\displaystyle \frac{l}{2}}+2$.

We summarize the ModSwitch_RNS operation as follows:

D-5.5.1 Comparing ModSwitch_RNS, ModRaise_RNS, and ModDrop_RNS

Given a big value $x\in {\mathbb{Z}}_q$ in an RNS vector, ModSwitch_RNS reduces its modulus from $q\to q^{\prime }$ and explicitly decreases the modulo value $x$ by the proportion of ${\displaystyle \frac{q^{\prime }}{q}}$ (i.e., it updates $x$ to $\lceil x\cdot {\displaystyle \frac{q^{\prime }}{q}}\rfloor$). On the other hand, ModDrop_RNS from $q\to q^{\prime }$ updates the modulo value from $x\to |x{|}_{q^{\prime }}$ (where $q^{\prime }$ divides $q$), which is different from decreasing $x$ by the proportion of ${\displaystyle \frac{q^{\prime }}{q}}$ like modulus switch. ModRaise_RNS from $q\to \mathit{𝑞𝑏}$ (where $q$ divides $\mathit{𝑞𝑏}$) increases the modulus without explicitly modifying the modulo value $x$, but it generates some $q$-overflow noise. ModSwitch_RNS and ModRaise_RNS generate some noise, whereas ModDrop_RNS does not generate any noise.