Learning With Errors (LWE) is a quantum robust method of cryptography. Initially we create a secret key value (s) and another value (e). Next we select a number of values (t[]) and calculate g[] = t[] x s + e. The values of g[] and t[] become our public key:
Learning With Errors (LWE) |
Outline
This is a method defined by Oded Regev in 2005 [here] and is known as LWE (Learning With Errors). It involves the difficulty of finding the values which solve:
\(t =g s + e\)
where you know t and g. The value of s becomes the secret value (or the secret key), and t and g can become the public key.
To decrypt all we have to do what divide by the private key value (s), and if the remainder is positive the message was "0", else if it was odd, the message was "1".
A sample run with a message of "0" gives:
Message to send: 0 Random values: [5, 8, 12, 16, 2, 6, 11, 3, 7, 10] ----------------------- Public key [37, 52, 72, 92, 22, 42, 67, 27, 47, 62] Selected values [52, 92, 27, 62, 37] Sum is: 270 Encrypted is: 270 Message received is 0
and with "1":
Message to send: 1 Random values: [5, 8, 12, 16, 2, 6, 11, 3, 7, 10] ----------------------- Public key [37, 52, 72, 92, 22, 42, 67, 27, 47, 62] Selected values [22, 42, 72, 92, 27] Sum is: 255 Encrypted is: 256 Message received is 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 public_key=[] vals = [5, 8, 12, 16, 2, 6, 11, 3, 7, 10] s = 5 e = 12 message = 1 file='1111' val=0 for x in range(0,len(vals)): public_key.append(vals[x]*s+e) print("Message to send:",message) print("Random values:",vals) print("-----------------------\n") res = random.sample(public_key, len(public_key)//2) print("Public key",public_key) print("Selected values",res) sum = np.sum(res) print('Sum is:',sum) if (message==1): sum=sum+1 print('Encrypted is:',sum) rem = sum % s if (rem%2==0): print('Message received is 0') else: print('Message received is 1')
A fun article on this is [here]