D-5.3 RNS-based ModDrop: ModDrop_RNS

ModDrop (§D-3.7, §D-4.6) is an operation of decreasing a ciphertext’s modulus from $q\to q^{\prime }$ (where $q^{\prime }$ divides $q$) without affecting the plaintext’s scaling factor(in the case of CKKS) or the noise’s scaling factor (in the case of BGV).

In an RNS-based ciphertext representation, ModDrop is equivalent to removing some of the base moduli in the ciphertext without affecting the scaling factor $\mathrm{\Delta }$. This can be achieved by converting the ciphertext’s base from $q$ to $\overline{q}$ where the base moduli set of $\overline{q}$ are a subset of that of $q$; that is, $\overline{q}$ divides $q$. Specifically, suppose that we have an input $(x_1,x_2,\cdots ,x_k)\in {\mathbb{Z}}_{q_1}\times {\mathbb{Z}}_{q_2}\times \cdots \times {\mathbb{Z}}_{q_k}$, and a new subset base $\overline{q}=q_1\cdot q_2\cdot \cdots \cdot q_{k^{\prime }}$, where $k^{\prime }<k$. In this setup, the fast base conversion from $q\to \overline{q}$ is equivalent to simply extracting the input value’s RNS residues associated with the base moduli $(q_1,q_2,\cdots ,q_{k^{\prime }})$. This is because of the following reasoning:

$\mathsf{\text{𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏}}({\{x_i\}}_{i=1}^k,q,\overline{q})={\left(\underset{i=1}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}|x_i\cdot z_i{|}_{q_i}\cdot y_{i}mod{q}_j\right)}_{j\in [1,k^{\prime }]}$

$=x+\mathit{𝑢𝑞}mod\overline{q}$ # Summary D-5.1 in §D-5.1

$=xmod\overline{q}$ # $\mathit{𝑢𝑞}$ gets eliminated because $\overline{q}$ divides $\mathit{𝑢𝑞}$

$=(x_1,x_2,\cdots ,x_{k^{\prime }})\in {\mathbb{Z}}_{q_1}\times {\mathbb{Z}}_{q_2}\times \cdots \times {\mathbb{Z}}_{q_{k^{\prime }}}$

Notice that the above fast base conversion from $q\to \overline{q}$ (where $\overline{q}$ divides $q$) does not generate any noise. This is different from the case of fast base conversion from $q\to b$ (Summary D-5.1 in §D-5.1) where $q$ and $b$ are co-prime, which generates the noise $|\mathit{𝑢𝑞}{|}_b$ (where integer $|u|\le {\displaystyle \frac{k}{2}}+1$).

The ModDrop operation is supported in all of BFV, BGV, and CKKS ciphertexts that are represented in RNS forms. However, note that ModDrop is possible only if the scaled plaintext (in the case of BFV and CKKS) or the scaled noise (in the case of BGV) does not exceed the ciphertext modulus after the mod-drop operation, because otherwise correct decryption is not possible. ModDrop_RNS is summarized as follows: