Public Key Encryption with Learning With Errors (LWE)

Learning With Errors (LWE) is a quantum robust method of cryptography and which can also be used for homomorphic encryption. Initially we create a secret value (s) and which is our private key. We then create a public key which is based on random numbers (A), and then generate another set of numbers (B) which is based on A, s and random errors e.

It is a method defined by Oded Regev in 2005 [here] and is known as LWE (Learning With Errors). First we select a random series of values for our public key (A). For example, let’s select 20 random values from 0 to 100:

[80, 86, 19, 62, 2, 83, 25, 47, 20, 58, 45, 15, 30, 68, 4, 13, 8, 6, 42, 92]

Next we add create a list (B) and were the elements are B_i=A_i s+e_i(mod q), and where s is a secret value, and e is a list of small random values (the error values). If we take a prime number (q) of 97, and an error array (e) of:

[3, 3, 4, 1, 3, 3, 4, 4, 1, 4, 3, 3, 2, 2, 3, 2, 4, 4, 1, 3]

we generate a list (B) of:

[15, 45, 2, 20, 13, 30, 32, 45, 4, 3, 34, 78, 55, 51, 23, 67, 44, 34, 17, 75]

The A and B list will be our public key, and s will be our secret key. We can now distribute A and B to anyone who wants to encrypt a message for us (but keep s secret). To…