There are a multitude of approaches in post-quantum cryptography that promise security in a world where Quantum Computers are powerful enough to break RSA using Shor's algorithm. Some interesting ones include isogeny based ones or lattices, to which Learning with Errors (LWE) belongs. The contribution of this post is a simple and easily modifiable example on how asymmetric encryption based on LWE works.
Initially, B creates an over-defined and solvable system of equations such as:
5a + 4b + c = 17 mod 20 3a + 10b + c = 19 mod 20 10a + 5b + 3c = 14 mod 20
c=3. Those three numbers are the private key of B.
Next, B adds errors to the equation system:
5a + 4b + c = 17+1 mod 20 3a + 10b + c = 19-2 mod 20 10a + 5b + 3c = 14+1 mod 20
and denotes the coefficients and the wrong values the public key:
5 4 1 18 3 10 1 17 10 5 3 15
with modulo 20.
A now wants to encrypt a message using B's public key and send it to B.
She goes bit by bit. We start with the very first bit of the message, which is
For each row of the public key she flips a coin. She sums up the rows come up
with tails. Let's for example assume row 1 and 3 came up. She sums up the
coefficients and values and ends up with:
15a + 9b + 4c = 18+15 mod 20 = 13 mod 20
Depending on the message bit, which in our example is 1, she adds an error:
- a large one if the bit is 1
- a small one if the bit is 0
In our case we change
13 mod 20 to for example
2 mod 20.
A sends to Bob the coefficients and the wrong value:
15 9 4 2
B now inserts the private key and calculates:
15a + 9b + 4c = 15*2 + 9*1 + 4*3 = 51 mod 20 = 11 mod 20
Since the value transmitted by A is 2 and this is a large error, B assumes the
bit was 1.
Likewise, if the bit would have been 0, A would have for example sent
12 mod 20
2 mod 20.
The reason this scheme works is that it is very easy to add errors to the
system of equations, but very tough to find the errors when
a, b, c are
And where is the lattice in this? The public key of B can be seen as a set of basis vectors in a lattice and the attacker needs to solve the Closest Vector Problem to find the good (real) vectors, which is very tough (polynomial runtime algorithms approximate the solution only within exponential quality).