Learning With Errors (LWE) is a quantum robust method of cryptography. 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\). An example of encryption with multiple bits is given here.
Public Key Encryption with Learning With Errors (LWE) |
Outline
This 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 \pmod 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 encrypt we take samples from the A and B lists, and take a message bit (M), and then calculate two values:
\(u = \sum(A_{samples}) \pmod q \)
\(v = \sum(B_{samples})+\frac{q}{2} M \pmod q \)
The encrypted message is (\(u,v\)). To decrypt, we calculate:
\( Dec = v - s u \pmod q\)
If \(Dec\) is less than \(\frac{q}{2}\), the message is a zero, else it is a 1.
A sample run is:
Message to send: 0 Public Key (A): [80, 86, 19, 62, 2, 83, 25, 47, 20, 58, 45, 15, 30, 68, 4, 13, 8, 6, 42, 92] Public Key (B): [15, 45, 2, 20, 13, 30, 32, 45, 4, 3, 34, 78, 55, 51, 23, 67, 44, 34, 17, 75] Errors (e): [3, 3, 4, 1, 3, 3, 4, 4, 1, 4, 3, 3, 2, 2, 3, 2, 4, 4, 1, 3] Secret key: 5 Prime number: 97 ----------------------- Sampling [18, 5, 8, 13, 11] U is 34 V is 83.0 Message is a 0
And a message of 1:
------Parameters and keys------- Message to send: 1 Public Key (A): [47, 27, 72, 89, 19, 64, 26, 79, 68, 83, 1, 76, 25, 65, 55, 82, 85, 14, 92, 5] Public Key (B): [45, 41, 73, 61, 0, 33, 35, 10, 53, 31, 7, 92, 30, 38, 83, 24, 41, 71, 74, 27] Errors (e): [4, 3, 4, 4, 2, 4, 2, 3, 4, 4, 2, 3, 2, 4, 2, 2, 4, 1, 2, 2] Secret key: 5 Prime number: 97 ------Sampling Process from public key------- Sampling [7, 5, 16, 8, 2] [ 79 10 ] [ 64 33 ] [ 85 41 ] [ 68 53 ] [ 72 73 ] ------Calculation of u and v ----------------- u: 77 v: 64.0 Result is 67.0 Message is a 1
Within Ring-LWE, which is the new crypto method implemented by Google, we use a set of numbers, known as polynomials for our values of t, g, s and e.
Coding
The following is an outline:
import sys import numpy as np import random import math nvals=20 B=[] e=[] s = 20 message = 1 q=97 A = random.sample(range(q), nvals) for x in range(0,len(A)): e.append(random.randint(1,4)) B.append((A[x]*s+e[x])%q) print("\n------Parameters and keys-------") print("Message to send:\t",message) print("Public Key (A):\t",A) print("Public Key (B):\t",B) print("Errors (e):\t\t",e) print("Secret key:\t\t",s) print("Prime number:\t\t",q) print("\n------Sampling Process from public key-------") sample= random.sample(range(nvals-1), nvals//4) print("Sampling",sample) u=0 v=0 for x in range(0,len(sample)): print("[",A[sample[x]],B[sample[x]],"]", end=' ') u=u+(A[sample[x]]) v= v+B[sample[x]] v=v+math.floor(q//2)*message v = v%q u = u%q print() print("\n------Calculation of u and v -----------------") print("u:\t\t",u) print("v:\t\t",v) res=(v-s*u) % q print("Result is\t",res) if (res>q/2): print("Message is a 1") else: print("Message is a 0")
A fun article on this is [here]