D-5.6 RNS-based Decryption

This subsection will explain how to efficiently decrypt RNS-based ciphertexts for BFV, CKKS, and BGV.

D-5.6.1 BFV Decryption: ${\mathsf{\text{𝖣𝖾𝖼}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖥𝖵}}}$

Suppose we have a BFV ciphertext $(A,B)$ such that $B=A\cdot S+\mathrm{\Delta }M+E$ (where $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$). We decrypt the ciphertext as follows: $M=\lceil {\displaystyle \frac{B-A\cdot S}{\mathrm{\Delta }}}\rfloor$ (Summary D-2.3 in §D-2.3). However, RNS does not allow direct division and rounding. Therefore, we need to express this divide-and-round operation in terms of addition and multiplication.

Let’s denote $\mathsf{\text{𝖼𝗍}}(s)=\mathrm{\Delta }m+e+\mathit{𝑘𝑞}$ (i.e., a decryption of ciphertext $\mathsf{\text{𝖼𝗍}}$ without modulo-$q$ reduction). In this description, we will consider only a single set of coefficients $m$, $e$, and $k$ extracted from polynomials $M$, $E$, and $K$ for simplicity.

As explained in §A-1.4, modulo arithmetic does not support direct division. Meanwhile, the special relation ${\displaystyle \frac{a}{b}}modp=a\cdot b^{-1}modp$ holds if $b$ divides $a$ and an inverse of $b$ modulo $p$ exists (i.e., $b$ and $p$ are co-prime). Inspired by this, we can express the decrypted plaintext $m$ as follows:

$m=\lceil {\displaystyle \frac{|\mathsf{\text{𝖼𝗍}}(s){|}_q}{\mathrm{\Delta }}}\rfloor =\lfloor {\displaystyle \frac{|\mathsf{\text{𝖼𝗍}}(s){|}_q}{\mathrm{\Delta }}}\rfloor +e_r$ $▹$ where $e_r\in [0,1]$ is a rounding error

$=\lfloor |\mathsf{\text{𝖼𝗍}}(s){|}_q\cdot {\displaystyle \frac{t}{q}}\rfloor +e_r+e_d$ $▹$ where $e_d=\lfloor {\displaystyle \frac{|\mathsf{\text{𝖼𝗍}}(s){|}_q}{\mathrm{\Delta }}}\rfloor -\lfloor |\mathsf{\text{𝖼𝗍}}(s){|}_q\cdot {\displaystyle \frac{t}{q}}\rfloor$ is a scaling error

$=\lfloor {\displaystyle \frac{t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q}{q}}\rfloor +e_r+e_d$

$={\displaystyle \frac{t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q-|t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q}{q}}+e_r+e_d$ $▹$ where $|t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q\equiv t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_{q}modq$, and therefore $t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q-|t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q$ is divisible by $q$

Now, we choose some prime number $\gamma$ which is co-prime to $t$ and $q$. Then, we derive the expression for $\gamma \cdot m$ as follows:

$\gamma \cdot m=\gamma \cdot \lceil {\displaystyle \frac{|\mathsf{\text{𝖼𝗍}}(s){|}_q}{\mathrm{\Delta }}}\rfloor$

$=\lceil {\displaystyle \frac{\gamma \cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q}{\mathrm{\Delta }}}\rfloor +e_s^{\prime }$ $▹$ where $e_s^{\prime }=\gamma \cdot \lceil {\displaystyle \frac{|\mathsf{\text{𝖼𝗍}}(s){|}_q}{\mathrm{\Delta }}}\rfloor -\lceil {\displaystyle \frac{\gamma \cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q}{\mathrm{\Delta }}}\rfloor$ is a multiplication error

$=\lfloor {\displaystyle \frac{\gamma \cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q}{\mathrm{\Delta }}}\rfloor +e_s^{\prime }+e_r^{\prime }$ $▹$ where $e_r^{\prime }\in [0,1]$ is a rounding error

$=\lfloor \gamma \cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q\cdot {\displaystyle \frac{t}{q}}\rfloor +e_s^{\prime }+e_r^{\prime }+e_d^{\prime }$ $▹$ where $e_d^{\prime }=\left(\lfloor {\displaystyle \frac{\gamma \cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q}{\mathrm{\Delta }}}\rfloor -\lfloor \gamma \cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q\cdot {\displaystyle \frac{t}{q}}\rfloor \right)$ is a scaling error

$=\lfloor {\displaystyle \frac{\gamma \cdot t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q}{q}}\rfloor +e_s^{\prime }+e_r^{\prime }+e_d^{\prime }$

$={\displaystyle \frac{\gamma \cdot t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q-|\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q}{q}}+e_s^{\prime }+e_r^{\prime }+e_d^{\prime }$

Next, we derive the expression for $|\gamma \cdot m{|}_{\mathit{𝛾𝑡}}$ as follows:

$|\gamma \cdot m{|}_{\mathit{𝛾𝑡}}={\left|{\displaystyle \frac{\gamma \cdot t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q-|\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q}{q}}+e_s^{\prime }+e_r^{\prime }+e_d^{\prime }\right|}_{\mathit{𝛾𝑡}}$

$={\left|{\displaystyle \frac{\gamma \cdot t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q-|\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q}{q}}\right|}_{\mathit{𝛾𝑡}}+|e_s^{\prime }{|}_{\mathit{𝛾𝑡}}+|e_r^{\prime }{|}_{\mathit{𝛾𝑡}}+|e_d^{\prime }{|}_{\mathit{𝛾𝑡}}$

$={\left|{\displaystyle \frac{\gamma \cdot t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q-|\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q}{q}}\right|}_{\mathit{𝛾𝑡}}+e_s^{\prime }+e_r^{\prime }+e_d^{\prime }$ $▹$ assuming $|e_s^{\prime }|\ll {\displaystyle \frac{\mathit{𝛾𝑡}}{2}}$ and $|e_r^{\prime }|\ll {\displaystyle \frac{\mathit{𝛾𝑡}}{2}}$ and $|e_d^{\prime }|\ll {\displaystyle \frac{\mathit{𝛾𝑡}}{2}}$

$=|(\gamma \cdot t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q-|\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q)\cdot q^{-1}{|}_{\mathit{𝛾𝑡}}+e_s^{\prime }+e_r^{\prime }+e_d^{\prime }$ $▹$ since $\gamma \cdot t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q-|\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q$ is divisible by $q$, and $q$ is co-prime to $\mathit{𝛾𝑡}$

$={\left|-|\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q\cdot q^{-1}\right|}_{\mathit{𝛾𝑡}}+e_s^{\prime }+e_r^{\prime }+e_d^{\prime }$ $▹$ since $\gamma \cdot t\cdot |\mathsf{\text{𝖼𝗍}}(s){|}_q$ is a multiple of $\mathit{𝛾𝑡}$

$=||\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q{|}_{\mathit{𝛾𝑡}}\cdot |-q^{-1}{|}_{\mathit{𝛾𝑡}}+e_s^{\prime }+e_r^{\prime }+e_d^{\prime }$

Given the above relation, notice that the computation result of $\mathsf{\text{𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏}}(\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s),q,\mathit{𝛾𝑡})\cdot |-q^{-1}{|}_{\mathit{𝛾𝑡}}$ can be expressed as follows:

$\mathsf{\text{𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏}}(\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s),q,\mathit{𝛾𝑡})\cdot |-q^{-1}{|}_{\mathit{𝛾𝑡}}$

$=||\mathit{𝛾𝑡}\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q+\mathit{𝑢𝑞}{|}_{\mathit{𝛾𝑡}}\cdot |-q^{-1}{|}_{\mathit{𝛾𝑡}}$ $▹$ where $|u|\le {\displaystyle \frac{k}{2}}+1$ for the base moduli $q_1,q_2,\cdots ,q_k$

$=||\mathit{𝛾𝑡}\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q\cdot |-q^{-1}{|}_{\mathit{𝛾𝑡}}-u{|}_{\mathit{𝛾𝑡}}$

$=|\gamma \cdot m{|}_{\mathit{𝛾𝑡}}-e_s^{\prime }-e_r^{\prime }-e_d^{\prime }-u$ $▹$ as we previously showed that $|\gamma \cdot m{|}_{\mathit{𝛾𝑡}}=||\gamma \cdot t\cdot \mathsf{\text{𝖼𝗍}}(s){|}_q{|}_{\mathit{𝛾𝑡}}\cdot |-q^{-1}{|}_{\mathit{𝛾𝑡}}++e_s^{\prime }+e_r^{\prime }+e_d^{\prime }$

$=y$ $▹$ let’s denote the above expression as $y$

Then, if $e_s^{\prime },e_r^{\prime },e_d^{\prime },u$ are small enough such that $|e_s^{\prime }+e_r^{\prime }+e_d^{\prime }+u|<\gamma$, then $|y{|}_{\gamma }=-e_s^{\prime }-e_r^{\prime }-e_d^{\prime }-u$ (as $|\gamma \cdot m{|}_{\mathit{𝛾𝑡}}mod\gamma =0$ as a multiple of $\gamma$). Therefore, we can effectively remove the noise terms $e_s^{\prime },e_r^{\prime },e_d^{\prime },u$ and derive $m$ as follows:

$|(y-|y{|}_{\gamma })\cdot |{\gamma }^{-1}{|}_t{|}_t$

$=||\gamma \cdot m{|}_{\mathit{𝛾𝑡}}\cdot |{\gamma }^{-1}{|}_t{|}_t$

$=||\gamma \cdot m{|}_t\cdot |{\gamma }^{-1}{|}_t{|}_t$ $▹$ since $||\gamma \cdot m{|}_{\mathit{𝛾𝑡}}{|}_t=|\gamma \cdot m{|}_t$

$=|m{|}_t$

, which is the final decryption of ct we wanted to compute. Let’s denote the RNS vector of $y$ as a $(y_{\gamma },y_t)\in {\mathbb{Z}}_{\gamma }\times {\mathbb{Z}}_t$. Then, we can efficiently compute the term $|(y-|y{|}_{\gamma })\cdot |{\gamma }^{-1}{|}_t{|}_t$ as follows:

$|(y-|y{|}_{\gamma })\cdot |{\gamma }^{-1}{|}_t{|}_t$

$=|(\stackrel{y}{\overbrace{|y_{\gamma }\cdot t\cdot |t^{-1}{|}_{\gamma }+y_t\cdot \gamma \cdot |{\gamma }^{-1}{|}_t{|}_{\mathit{𝛾𝑡}}}}-\stackrel{|y{|}_{\gamma }}{\overbrace{|y_{\gamma }\cdot t\cdot |t^{-1}{|}_{\gamma }+y_t\cdot \gamma \cdot |{\gamma }^{-1}{|}_t{|}_{\gamma }}})\cdot |{\gamma }^{-1}{|}_t{|}_t$

$=|(\stackrel{y}{\overbrace{|y_{\gamma }\cdot t\cdot |t^{-1}{|}_{\gamma }+y_t\cdot \gamma \cdot |{\gamma }^{-1}{|}_t{|}_t}}-\stackrel{|y{|}_{\gamma }}{\overbrace{|y_{\gamma }\cdot t\cdot |t^{-1}{|}_{\gamma }+y_t\cdot \gamma \cdot |{\gamma }^{-1}{|}_t{|}_{\gamma }}})\cdot |{\gamma }^{-1}{|}_t{|}_t$ $▹$ since $||y{|}_{\mathit{𝛾𝑡}}{|}_t=|y{|}_t$

$=|(\stackrel{y}{\overbrace{|y_{\gamma }\cdot t\cdot |t^{-1}{|}_{\gamma }+y_t\cdot \gamma \cdot |{\gamma }^{-1}{|}_t{|}_t}}-\stackrel{|y{|}_{\gamma }}{\overbrace{|y_{\gamma }\cdot t\cdot |t^{-1}{|}_{\gamma }{|}_{\gamma }}})\cdot |{\gamma }^{-1}{|}_t{|}_t$ $▹$ since $y_t\cdot \gamma \cdot |{\gamma }^{-1}{|}_{t}mod\gamma =0$

$=|(\stackrel{y}{\overbrace{|y_t\cdot \gamma \cdot |{\gamma }^{-1}{|}_t{|}_t}}-\stackrel{|y{|}_{\gamma }}{\overbrace{|y_{\gamma }\cdot t\cdot |t^{-1}{|}_{\gamma }{|}_{\gamma }}})\cdot |{\gamma }^{-1}{|}_t{|}_t$ $▹$ since $y_{\gamma }\cdot t\cdot |t^{-1}{|}_{\gamma }modt=0$

$=|(y_t-y_{\gamma })\cdot |{\gamma }^{-1}{|}_t{|}_t$ $▹$ since $|\gamma \cdot {\gamma }^{-1}{|}_t=1$ and $|t\cdot t^{-1}{|}_{\gamma }=1$

We summarize ${\mathsf{\text{𝖣𝖾𝖼}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖥𝖵}}}$ as follows:

D-5.6.2 CKKS and BGV Decryption

CKKS and BGV ciphertexts can be decrypted efficiently by performing the ModDrop operation (Summary D-5.4 in §D-5.4) to the lowest multiplicative level. After this, there remains only a single ciphertext modulus in the RNS base, so the regular decryption algorithm can be executed efficiently without any RNS components.