This demo illustrates the Learning With Errors (LWE) encryption scheme. You can modify the parameters, private key, error vector, message bit, and selected indices to see how they affect the encryption and decryption process.

To learn the mathematical foundations of LWE-based encryption, you can read my blog post Kyber Part 1: Learning With Errors - The Math That Makes Post-Quantum Cryptography Possible.

The private key $s \in \mathbb{Z}_p^n$ is generated at random.

$m$ random vectors $a_i \in \mathbb{Z}_p^n$ are generated to produce a $m \times n$ matrix $A$, and the error vector $e \in \mathbb{Z}_p^m$ is generated with small random values. Then, the vector $b \in \mathbb{Z}_p^m$ is computed as:

$$ \displaystyle As +e = \begin{pmatrix} - \ a_1\ -\\ - \ a_2\ -\\ \vdots \\ - \ a_m\ - \end{pmatrix} \begin{pmatrix} s_1\\ s_2\\ \vdots\\ s_n \end{pmatrix} + \begin{pmatrix} e_1\\ e_2\\ \vdots\\ e_m \end{pmatrix} = b $$

The public key is the pair $(A, b)$.

The message that is encrypted is a single bit.

To encrypt a message a random subset of the row vectors of matrix $A$ is selected.

Let $S$ be the set of selected indices. We compute $a_e = \sum_{i\in S} a_i$ and $b_e = \sum_{i\in S} b_i$.

Let $v = b_e + \lfloor p/2 \rfloor \cdot m $. The ciphertext is the pair $(a_e, v )$.

We compute $v - a_e \cdot s \mod p$. If the result is closer to 0 than to $\lfloor p/2 \rfloor$, then the decrypted message is 0; otherwise, it is 1.