B-2.3 Decryption

1.

Given the ciphertext $(\overrightarrow{a},b)$ where $b=\overrightarrow{a}\cdot \overrightarrow{s}+\mathrm{\Delta }\cdot m+e\in {\mathbb{Z}}_q$, compute $b-\overrightarrow{a}\cdot \overrightarrow{s}$, which gives the same value as $\mathrm{\Delta }\cdot m+e\in {\mathbb{Z}}_q$.

2.

Round $\mathrm{\Delta }\cdot m+e\in {\mathbb{Z}}_q$ to the nearest multiple of $\mathrm{\Delta }$ (i.e., round it as a base $\mathrm{\Delta }$ number), which is denoted as $\lceil \mathrm{\Delta }\cdot m+e{\rfloor }_{\mathrm{\Delta }}$. This rounding operation successfully eliminates $e$ and gives $\mathrm{\Delta }m$, provided $e$ is small enough to be $e<{\displaystyle \frac{\mathrm{\Delta }}{2}}$. If $e\ge {\displaystyle \frac{\mathrm{\Delta }}{2}}$, then some of the higher bits of the noise $e$ will overlap with the plaintext $m$, won’t be blown away, and will corrupt some lower bits of the plaintext $m$.

3.

Compute ${\displaystyle \frac{\mathrm{\Delta }m}{\mathrm{\Delta }}}$, which is equivalent to right-shifting $\lceil \mathrm{\Delta }\cdot m+e{\rfloor }_{\mathrm{\Delta }}$ by ${\text{log}}_2\mathrm{\Delta }$ bits. (Here we assume $\mathrm{\Delta }$ is a power of 2; if $\mathrm{\Delta }$ is not a power of 2, scaling up or down $m$ by $\mathrm{\Delta }$ is equivalent to multiplying or dividing the value by $\mathrm{\Delta }$.)

The LWE decryption formula is summarized as follows:

During decryption, the secret key owner can subtract $\overrightarrow{a}\cdot \overrightarrow{s}$ from $b$ because he can directly compute $\overrightarrow{a}\cdot \overrightarrow{s}$ by using his secret key $\overrightarrow{s}$.

The reason we scaled the plaintext $m$ by $\mathrm{\Delta }$ is: (i) to left-shift $m$ by ${\text{log}}_2\mathrm{\Delta }$ bits and separate it from the noise $e$ in the lower bits during encryption, whereas $e$ is essential to make it hard for the attacker to guess $m$ or $\overrightarrow{s}$; and (ii) to eliminate $e$ in the lower bits by right-shifting it by ${\text{log}}_2\mathrm{\Delta }$ bits without compromising $m$ in the higher bits during decryption. The process of right-shifting (i.e., scaling) the plaintext $m$ by ${\text{log}}_2\mathrm{\Delta }$ bits, followed by adding the noise $e$, is illustrated in Figure 8.

B-2.3.1 In the Case of $t$ not Dividing $q$

In Summary B-2.2 (§B-2.2), we assumed that $t$ divides $q$. In this case, there is no upper or lower limit on the size of plaintext $m$: its value is allowed to wrap around modulo $t$ indefinitely, yet the decryption works correctly. This is because any $m$ value greater than $t$ will be correctly modulo-reduced by $t$ when we perform modulo reduction by $q$ during decryption.

On the other hand, suppose that $t$ does not divide $q$. In such a case, we set the scaling factor as $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$. Then, provided $q\gg t$, the decryption works correctly even if $m$ is a large value that wraps around $t$. We will show why this is so.

In this subsection’s analysis, we choose $t$ to be an odd (prime) number, which is the general FHE practice for computational efficiency reasons (see §A-10.6.1). We assume the use of the centered residue system, where the plaintext domain is $\left[-{\displaystyle \frac{t-1}{2}},{\displaystyle \frac{t-1}{2}}\right]$ and the ciphertext domain is $\left[-{\displaystyle \frac{q}{2}},{\displaystyle \frac{q}{2}}-1\right]$. We denote plaintext $mmodt$ as $m=m^{\prime }+\mathit{𝑘𝑡}$, where $m^{\prime }\in {\mathbb{Z}}_t$, and $k$ is an integer that represents the $t$-overflow portions of $m$. We set the plaintext scaling factor as $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$. Then, the noise-added and $\mathrm{\Delta }$-scaled plaintext can be expressed as follows:

$\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m+e$

$=\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot \mathit{𝑘𝑡}+e$ $▹$ applying $m=m^{\prime }+\mathit{𝑘𝑡}$

$=\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+{\displaystyle \frac{q}{t}}\cdot \mathit{𝑘𝑡}-\left({\displaystyle \frac{q}{t}}-\lfloor {\displaystyle \frac{q}{t}}\rfloor \right)\cdot \mathit{𝑘𝑡}+e$

$=\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+\mathit{𝑞𝑘}-\left({\displaystyle \frac{q}{t}}-\lfloor {\displaystyle \frac{q}{t}}\rfloor \right)\cdot \mathit{𝑘𝑡}+e$

$=\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+\mathit{𝑞𝑘}-𝜖\cdot \mathit{𝑘𝑡}+e$ $▹$ where $𝜖={\displaystyle \frac{q}{t}}-\lfloor {\displaystyle \frac{q}{t}}\rfloor$, a decimal value between $[0,1)$

Remember that the LWE decryption relation: ${\displaystyle \frac{b-\overrightarrow{a}\cdot \overrightarrow{s}modq}{\mathrm{\Delta }}}modt={\displaystyle \frac{\mathrm{\Delta }m+emodq}{\mathrm{\Delta }}}modt$. Therefore, from the above expression, we can decrypt the message by computing as follows:

$\lceil {\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot \left(b-\overrightarrow{a}\cdot \overrightarrow{s}modq\right)\rfloor modt$

$=\lceil {\displaystyle \frac{1}{\mathrm{\Delta }}}\cdot \left(\mathrm{\Delta }m+emodq\right)\rfloor modt$

$=\lceil {\displaystyle \frac{1}{\lfloor \frac{q}{t}\rfloor }}\cdot \left(\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot (m^{\prime }+\mathit{𝑘𝑡})+emodq\right)\rfloor modt$

$=\lceil {\displaystyle \frac{1}{\lfloor \frac{q}{t}\rfloor }}\cdot \left(\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot \mathit{𝑘𝑡}+emodq\right)\rfloor modt$

$=\lceil {\displaystyle \frac{1}{\lfloor \frac{q}{t}\rfloor }}\cdot \left(\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+\left({\displaystyle \frac{q}{t}}-𝜖\right)\cdot \mathit{𝑘𝑡}+emodq\right)\rfloor modt$

$=\lceil {\displaystyle \frac{1}{\lfloor \frac{q}{t}\rfloor }}\cdot \left(\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+\mathit{𝑘𝑞}-\mathit{𝜖𝑘𝑡}+emodq\right)\rfloor modt$

$=\lceil {\displaystyle \frac{1}{\lfloor \frac{q}{t}\rfloor }}\cdot \left(\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }-\mathit{𝜖𝑘𝑡}+emodq\right)\rfloor modt$

In order for the decryption to work, we ideally want to eliminate the inner modulo $q$ reduction. That is, assuming the centered residue system $\left[-{\displaystyle \frac{q}{2}},{\displaystyle \frac{q}{2}}-1\right]$, we want $-{\displaystyle \frac{q}{2}}\le \lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }-\mathit{𝜖𝑘𝑡}+e<{\displaystyle \frac{q}{2}}$, or more strictly, $\left|\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }-\mathit{𝜖𝑘𝑡}+e\right|<{\displaystyle \frac{q}{2}}$.

To ensure these conditions hold, we will make a special assumption: $|-\mathit{𝜖𝑘𝑡}+e|<{\displaystyle \frac{\mathrm{\Delta }}{2}}$. Applying this assumption to the expression above, we can derive the following relation:

$\left|\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }-\mathit{𝜖𝑘𝑡}+e\right|$

$\le \left|\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }\right|+\left|-\mathit{𝜖𝑘𝑡}+e\right|$

$\le \left|\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot {\displaystyle \frac{t-1}{2}}\right|+\left|-\mathit{𝜖𝑘𝑡}+e\right|$ $▹$ we assume $t$ is an odd prime, as that’s the general FHE practice

$\le \left|{\displaystyle \frac{q}{t}}\cdot {\displaystyle \frac{t-1}{2}}\right|+\left|-\mathit{𝜖𝑘𝑡}+e\right|$

$={\displaystyle \frac{q}{2}}-{\displaystyle \frac{q}{2t}}+\left|-\mathit{𝜖𝑘𝑡}+e\right|$

$<{\displaystyle \frac{q}{2}}-{\displaystyle \frac{q}{2t}}+{\displaystyle \frac{\mathrm{\Delta }}{2}}$ $▹$ applying our special assumption $|-\mathit{𝜖𝑘𝑡}+e|<{\displaystyle \frac{\mathrm{\Delta }}{2}}$

$={\displaystyle \frac{q}{2}}+{\displaystyle \frac{1}{2}}\cdot \left(\mathrm{\Delta }-{\displaystyle \frac{q}{t}}\right)$

$<{\displaystyle \frac{q}{2}}$ $▹$ since $\mathrm{\Delta }<{\displaystyle \frac{q}{t}}$

Therefore, if we assume $|-\mathit{𝜖𝑘𝑡}+e|<{\displaystyle \frac{\mathrm{\Delta }}{2}}$, then $\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }-\mathit{𝜖𝑘𝑡}+emodq$ can be simplified to $\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }-\mathit{𝜖𝑘𝑡}+e$. We continue with the following derivation:

$\lceil {\displaystyle \frac{1}{\lfloor \frac{q}{t}\rfloor }}\cdot \left(\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }-\mathit{𝜖𝑘𝑡}+emodq\right)\rfloor modt$

$=\lceil {\displaystyle \frac{1}{\lfloor \frac{q}{t}\rfloor }}\cdot \left(\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }-\mathit{𝜖𝑘𝑡}+e\right)\rfloor modt$

$=\lceil m^{\prime }+{\displaystyle \frac{-\mathit{𝜖𝑘𝑡}+e}{\lfloor \frac{q}{t}\rfloor }}\rfloor modt$

$=m^{\prime }+\lceil {\displaystyle \frac{-\mathit{𝜖𝑘𝑡}+e}{\lfloor \frac{q}{t}\rfloor }}\rfloor modt$ $▹$ since $\lceil m^{\prime }\rfloor =m^{\prime }$

$=m^{\prime }modt$ $▹$ applying special assumption $|-\mathit{𝜖𝑘𝑡}+e|<{\displaystyle \frac{\mathrm{\Delta }}{2}}={\displaystyle \frac{\lfloor \frac{q}{t}\rfloor }{2}}$

To summarize, if we set the plaintext’s scaling factor as $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$ and $t$ is an odd (prime) number, the decryption works correctly as long as the following error-bounding condition holds: $|-\mathit{𝜖𝑘𝑡}+e|<{\displaystyle \frac{\mathrm{\Delta }}{2}}={\displaystyle \frac{\lfloor \frac{q}{t}\rfloor }{2}}$. This condition (i.e., decryption) breaks if: (1) the noise $e$ is too large relative to $q$; (2) the plaintext modulus $t$ is too large relative to $q$; or (3) the plaintext value wraps around $t$ too many times (i.e., $k$ is too large). A general solution to ensure all these error bound conditions is to set the ciphertext modulus $q$ to be sufficiently large. To put it differently, if $q\gg t$ and $q\gg e$, then the error bound holds.

We can generalize the formula for the plaintext’s scaling factor in Summary B-2.2 (in §B-2.2) as $\lfloor {\displaystyle \frac{q}{t}}\rfloor$, where $t$ is an odd (prime) number.