B-1.2 LWE Cryptosystem

The LWE cryptosystem uses the following encryption formula: $b=\overrightarrow{s}\cdot \overrightarrow{a}+\mathrm{\Delta }\cdot m+e$ (where $\overrightarrow{s}$ is a secret key, $\overrightarrow{a}$ is a publicly known random vector picked per encryption, $m$ is a plaintext, $e$ is small noise randomly picked per encryption from a normal distribution, and $b$ is a ciphertext). $\mathrm{\Delta }$ is a scaling factor of the plaintext $M$ (shifting $m$ by ${\text{log}}_2\mathrm{\Delta }$ bits to the left). Before encrypting the plaintext, we left-shift the plaintext several bits (i.e., ${\text{log}}_2\mathrm{\Delta }$ bits) to secure sufficient space to store the error in the lower bits.

Figure 8 visually illustrates the term $\mathrm{\Delta }\cdot m+e$, where the plaintext $m$ left-shifted by ${\text{log}}_2\mathrm{\Delta }$ bits and noised by the noise $e$. The actual encryption and decryption formulas are as follows:

$\lfloor {\rceil }_{\mathrm{\Delta }}$ means rounding the number to the nearest multiple of $\mathrm{\Delta }$. For example, $\lfloor 16{\rceil }_{10}=20$, which is rounding 16 to the nearest multiple of 10. As another example, $\lfloor 17{\rceil }_8=16$, which rounds 17 to the nearest multiple of 8 (note that 17 is closer to 16 than to 24; thus, it is rounded to 16).

Correctness: In the decryption scheme, computing $b^{⟨i⟩}-\overrightarrow{s}\cdot {\overrightarrow{a}}^{⟨i⟩}$ gives $\mathrm{\Delta }\cdot m^{⟨i⟩}+e^{⟨i⟩}$, which is Figure 8. Then, $\lceil \mathrm{\Delta }\cdot m^{⟨i⟩}+e^{⟨i⟩}{\rfloor }_{\mathrm{\Delta }}$ (i.e., rounding the value to the nearest multiple of $\mathrm{\Delta }$) gives $\mathrm{\Delta }\cdot m^{⟨i⟩}$, provided the added noise $|e^{⟨i⟩}|<\frac{\mathrm{\Delta }}{2}$. That is, if the noise is less than $\frac{\mathrm{\Delta }}{2}$, it will disappear during the rounding. Finally, right-shifting $\mathrm{\Delta }\cdot m^{⟨i⟩}$ by ${\text{log}}_2\mathrm{\Delta }$ bits gives $m^{⟨i⟩}$. To summarize, if we ensure $|e^{⟨i⟩}|<\frac{\mathrm{\Delta }}{2}$ (which is why the noise $e^{⟨i⟩}$ should be smaller than this threshold), then we can eliminate $e^{⟨i⟩}$ during the decryption’s rounding process and retrieve the original $\mathrm{\Delta }\cdot m^{⟨i⟩}$. The reason we scaled $m^{⟨i⟩}$ by $\mathrm{\Delta }$ is to: (i) create space for storing $e^{⟨i⟩}$ in the lower bits during encryption such that the noise bits do not interfere with the plaintext bits (to avoid corrupting the plaintext bits); and (ii) blow away the noise $e^{⟨i⟩}$ stored in the lower bits during decryption without corrupting the plaintext $m^{⟨i⟩}$.

Security: Given that an attacker has a large list of $({\overrightarrow{a}}^{⟨i⟩},b^{⟨i⟩})$ (i.e., many ciphertexts), it is almost impossible for them to derive $\overrightarrow{s}$, due to the random noise $e^{⟨i⟩}$ added in each encryption (which is a search-hard problem described in §B-1.1). This is because even small added unknown noises $e^{⟨i⟩}$ greatly change the mathematical solution for $\overrightarrow{s}$ that satisfies all the $b^{⟨i⟩}=\overrightarrow{s}\cdot {\overrightarrow{a}}^{⟨i⟩}+\mathrm{\Delta }\cdot m^{⟨i⟩}+e^{⟨i⟩}$ equations.

Even in the case that the attacker has a large list of $({\overrightarrow{a}}^{(j)},b^{(j)})$ generated for the same ciphertext $m^{⟨i⟩}$ (where each ciphertext used different ${\overrightarrow{a}}^{(j)}$ and $e^{(j)}$ to encrypt the same $m^{⟨i⟩}$), he still cannot derive $m^{⟨i⟩}$, because a randomly picked different noise $e^{(j)}$ is used for every $({\overrightarrow{a}}^{(j)},b^{(j)})$ and is accumulated over ciphertexts, which exponentially complicates the difficulty of the linear algebra involved in solving $\overrightarrow{s}$. Also, in the actual cryptosystem (§B-2), the publicly known random vector ${\overrightarrow{a}}^{⟨i⟩}$ and the secret key $\overrightarrow{s}$ are not a single number but a long vector comprising many random numbers. Thus, adding ${\overrightarrow{a}}^{⟨i⟩}\cdot \overrightarrow{s}$ to $\mathrm{\Delta }{m}^{⟨i⟩}+e^{⟨i⟩}$ increases the entropy of randomness against the attack.

To summarize, lattice-based cryptography hides plaintext by adding the encryption component $\overrightarrow{s}\cdot \overrightarrow{a}$ to it, along with a small random noise $e$. During decryption, the secret key owner re-creates this encryption component $\overrightarrow{a}\cdot \overrightarrow{s}$ by using her $\overrightarrow{s}$ and removes it. She then removes the noise $e$ using the rounding technique and finally right-shifts the remaining $\mathrm{\Delta }m$ by ${\text{log}}_2\mathrm{\Delta }$ bits to get $m$.