B-1.2 LWE Cryptosystem

The LWE cryptosystem uses the following encryption formula: $B=S\cdot A+\mathrm{\Delta }\cdot M+E$ (where $S$ is a secret key, $A$ is a public key randomly picked per encryption, $M$ is a plaintext, $E$ is a 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) in order 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 is rounding 17 to the nearest multiple of 8 (note that 17 is closer to 16 than 24, thus it is rounded to 16).

Correctness: In the decryption scheme, computing $B^{⟨i⟩}-S\cdot 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 blow away $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 the 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 an attacker has a large list of $(A^{⟨i⟩},B^{⟨i⟩})$ (i.e., many ciphertexts), it’s almost impossible for him to derive $S$, because of 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 $S$ that satisfies all the $B^{⟨i⟩}=S\cdot A^{⟨i⟩}+\mathrm{\Delta }\cdot M^{⟨i⟩}+E^{⟨i⟩}$ equations.

Even in the case that the attacker has a large list of $(A^{(j)},B^{(j)})$ generated for the same ciphertext $M^{⟨i⟩}$ (where each ciphertext used different $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 $(A^{(j)},B^{(j)})$ and gets accumulated over ciphertexts, which exponentially complicates the difficulty of the linear algebra of solving $S$. Also, in the actual cryptosystem (§B-2), the public key $A^{⟨i⟩}$ and the secret key $S$ are not a single number, but a long vector comprising many random numbers. Thus, adding $A^{⟨i⟩}\cdot S$ to $\mathrm{\Delta }{M}^{⟨i⟩}+E^{⟨i⟩}$ adds a higher entropy of randomness against the attack.

To summarize, the lattice-based cryptography hides a plaintext by adding the encryption component $S\cdot A$ to it as well as a small random noise $E$. During decryption, the secret key owner re-creates this encryption component $A\cdot S$ by using her $S$ and removes it, and then also removes the noise $E$ by the rounding technique, and finally right-shifts the remaining $\mathrm{\Delta }M$ by ${\text{log}}_2\mathrm{\Delta }$ bits to get $M$.