C-4 GLWE Modulus Switching

In the GLWE cryptosystem, modulus switching is a process of changing a ciphertext’s modulo domain to a smaller (or larger) one, while ensuring that the ciphertext still decrypts to the same plaintext. For example, suppose we have the ciphertext ${\mathsf{\text{𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }m)\in {\mathbb{Z}}_q^{k+1}$. If we switch the ciphertext’s modulo from $q\to q^{\prime }$, then the ciphertext is converted into ${\mathsf{\text{𝖫𝖶𝖤}}}_{S,\sigma }\left(\mathrm{\Delta }{\displaystyle \frac{q^{\prime }}{q}}m\right)\in {\mathbb{Z}}_{q^{\prime }}^{k+1}$. The ciphertext’s all other components such as the noise ($e$) and public keys ($a_0,a_1,\cdots ,a_{k-1}$, $b$) are scaled by ${\displaystyle \frac{q^{\prime }}{q}}$, becoming $\lceil e{\displaystyle \frac{q^{\prime }}{q}}\rfloor$, $\left(\lceil a_0{\displaystyle \frac{q^{\prime }}{q}}\rfloor ,\lceil a_1{\displaystyle \frac{q^{\prime }}{q}}\rfloor ,\cdots ,\lceil a_{k-1}{\displaystyle \frac{q^{\prime }}{q}}\rfloor ,\lceil b{\displaystyle \frac{q^{\prime }}{q}}\rfloor \right)$. To switch the modulo of an LWE ciphertext, we use the modulo rescaling technique learned from §A-12. The same modulus switching technique can also be applied to RLWE ciphertexts. In this section, we will show how to switch (i.e., rescale) the modulo of LWE and RLWE ciphertexts and prove its correctness.