D-5.6 BGV’s RNS-based Modulus Switch: ${\mathsf{\text{𝖬𝗈𝖽𝖲𝗐𝗂𝗍𝖼𝗁}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖦𝖵}}}$

BGV’s RNS-based modulus switch is not computed by ModSwitch_RNS, because BGV’s original non-RNS modulus switch (Summary D-4.7 in §D-4.7) is performed in a different manner than BFV or CKKS’s non-RNS modulus switch (Summary C-4.4 in §C-4.4). BGV’s non-RNS modulus switch is computed as follows:

$(A^{\prime },B^{\prime })=\left(\lceil {\displaystyle \frac{\widehat{q}}{q_l}}A\rfloor ,\lceil {\displaystyle \frac{\widehat{q}}{q_l}}\cdot B\rfloor \right)\in R_{⟨n,\widehat{q}⟩}^2$

${𝜖}_A^{\prime }=\widehat{q}\cdot A-q_l\cdot A^{\prime }$ # where ${𝜖}_A^{\prime }\in {\mathbb{Z}}_{q_l}$

${𝜖}_B^{\prime }=\widehat{q}\cdot B-q_l\cdot B^{\prime }$ # where ${𝜖}_B^{\prime }\in {\mathbb{Z}}_{q_l}$

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

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

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

Therefore, BGV’s RNS-based modulus switch only needs to compute the above formulas for $\widehat{A}$ and $\widehat{B}$ based on RNS’s $\text{(+,⋅)}$ arithmetic. In the above computations, the only part that cannot be directly computed by RNS-based $\text{(+,⋅)}$ operations is the rounding in $\lceil {\displaystyle \frac{\widehat{q}}{q_l}}A\rfloor$ and $\lceil {\displaystyle \frac{\widehat{q}}{q_l}}\cdot B\rfloor$. This rounding can be performed in RNS by using ${\mathsf{\text{𝖣𝖾𝖼}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖥𝖵}}}$, by setting $q=q_l$ and $t=\widehat{q}$.