About the author:
Daniel is CTO at rhome GmbH, and Co-Founder at Aqarios GmbH. He holds a M.Sc. in Computer Science from LMU Munich, and has published papers in reinforcement learning and quantum computing. He writes about technical topics in quantum computing and startups.
jrnl · home about list ventures publications LinkedIn Join my Slack

# Learning with Errors Problem Example in Post Quantum Cryptography

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

with a=2, b=1 and 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 example 1. 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 instead of 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 unknown.

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).

Published on