B-2.3 Decryption

1.

Given the ciphertext $(A,b)$ where $b=A\cdot S+\mathrm{\Delta }\cdot m+e\in {\mathbb{Z}}_q$, compute $b-A\cdot 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 the plaintext $m$, won’t be blown away and 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.

The LWE decryption formula is summarized as follows:

During decryption, the secret key owner can subtract $A\cdot S$ from $b$ because he can directly compute $A\cdot S$ by using his secret key $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 $S$; and (ii) to eliminate $e$ in the lower bits by right-shifting it by $\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 do 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.

We can denote plaintext $mmodt$ as $m=m^{\prime }+\mathit{𝑘𝑡}$, where $m^{\prime }\in {\mathbb{Z}}_t$ and $k$ are some integers we use to represent the modulo $t$ wrap-around value portion of $m$. And we set the plaintext scaling factor as $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$. Then, the noise-added scaled plaintext value is 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$ # by applying $m=m^{\prime }+\mathit{𝑘𝑡}$

$=\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+{\displaystyle \frac{q}{t}}\cdot \mathit{𝑘𝑡}-({\displaystyle \frac{q}{t}}-\lfloor {\displaystyle \frac{q}{t}}\rfloor )\cdot \mathit{𝑘𝑡}+e$ # where $0\le {\displaystyle \frac{q}{t}}-\lfloor {\displaystyle \frac{q}{t}}\rfloor <1$

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

We treat the above noisy scaled ciphertext as $=\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+\mathit{𝑞𝑘}-e^{\prime }+e$, where $e^{\prime }=\mathit{𝑘𝑡}$, the maximum possible value of $\lfloor {\displaystyle \frac{q}{t}}\rfloor )\cdot \mathit{𝑘𝑡}$. In other words, we overestimate the noise caused by $({\displaystyle \frac{q}{p}}-\lfloor {\displaystyle \frac{q}{t}}\rfloor )\cdot \mathit{𝑘𝑡}$ to $\mathit{𝑘𝑡}$, because the maximum value this term can become is less than $\mathit{𝑘𝑡}$.

Given the LWE decryption relation $b-A\cdot Smodq=\mathrm{\Delta }m+e$, we can decrypt the above message by performing:

$\lceil {\displaystyle \frac{1}{\lfloor \frac{q}{t}\rfloor }}\cdot \left(\lfloor {\displaystyle \frac{q}{t}}\rfloor \cdot m^{\prime }+\mathit{𝑞𝑘}-e^{\prime }+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{𝑘𝑡}+e\right)\rfloor modt$

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

$=m^{\prime }$ # provided ${\displaystyle \frac{\mathit{𝑘𝑡}+e}{\lfloor \frac{q}{t}\rfloor }}<{\displaystyle \frac{1}{2}}$

To summarize, if we set the plaintext’s scaling factor as $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$ where $t$ does not divide $q$, the decryption works correctly as far as the error bound ${\displaystyle \frac{\mathit{𝑘𝑡}+e}{\lfloor \frac{q}{t}\rfloor }}<{\displaystyle \frac{1}{2}}$ holds. This error bound can break if: (1) the noise $e$ is too large; (2) the plaintext modulus $t$ is too large; and (3) the plaintext value wraps around $t$ too many times (i.e., $k$ is too large). A solution to ensure ${\displaystyle \frac{\mathit{𝑘𝑡}+e}{\lfloor \frac{q}{t}\rfloor }}<{\displaystyle \frac{1}{2}}$ is that the ciphertext modulus $q$ is sufficiently large. To put it differently, if $q\gg t$, then the error bound will hold.

Therefore, 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$ does not necessarily divide $q$.