Multi-bit public key encryption with Learning With Errors (LWE)
Multi-bit public key encryption with Learning With Errors (LWE)
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. In this case we will show how a 4-bit value can be encrypted. In this case we will convert an integer to a 4-bit value, and then cipher each of the bits. This is achieved by generating a public key, and then sampling the public key for each of the bits.
This is a method defined by Oded Regev in 2005 [here] and is known as LWE. 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 Bi=Ais+ei(modq), 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 Aand 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=∑(Asamples)(mod q)
v=∑(Bsamples)+q/2 M(mod q)
The encrypted message is (u,v). To decrypt, we calculate:
Dec=v−su(mod q)
If Dec is less than q/2, the message is a zero, else it is a 1.
With multiple bits, we basically take our value and then convert into bits. Next we cipher each bit by taking a random sample from the public key.
A sample run with a value of 4 is [here]:
------Parameters and keys-------
Value to cipher: 4
Public Key (A): [6, 38, 90, 83, 51, 15, 31, 40, 18, 0, 10, 89, 93, 88, 32, 52, 24, 86, 82, 92]
Public Key (B): [31, 94, 66, 28, 65, 78, 60, 10, 91, 2, 53, 61, 80, 55, 65, 67, 24, 45, 26, 73]
Errors (e): [1, 1, 4, 1, 4, 3, 2, 4, 1, 2, 3, 4, 3, 3, 2, 1, 1, 3, 4, 1]
Secret key: 5
Prime number: 97
------Sampling Process from public key-------
Bits to be ciphered: [0, 0, 1, 0, 0, 0, 0, 0]
[13, 6, 14, 9, 8]
[18, 11, 9, 6, 0]
[8, 13, 11, 3, 4]
[1, 10, 6, 13, 3]
------Calculation of u and v -----------------
u1,v1: 72 79.0
u2,v2: 14 83.0
u3,v3: 38 57.0
u4,v4: 56 96.0
------Results -----------------
Result bit0 is 0
Result bit1 is 0
Result bit2 is 1
Result bits is 0
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.
The following is an outline of the coding [here]:
import sys
import numpy as np
import random
import math
nvals=20
B=[]
e=[]
s = 20
M = 5
q=97
def get_uv(A,B,M,q):
u=0
v=0
sample= random.sample(xrange(nvals-1), nvals/4)
print sample
for x in range(0,len(sample)):
u=u+(A[sample[x]])
v= v+B[sample[x]]
v=v+math.floor(q/2)*M
return u%q,v%q
def get_result(u,v,q):
res=(v-s*u) % q
if (res>q/2):
return 1
return 0
def tobits(val):
l = [0]*(8)
l[0]=val & 0x1
l[1]=(val & 0x2)>>1
l[2]=(val & 0x4)>>2
l[3]=(val & 0x8)>>3
return l
A = random.sample(xrange(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 "Value to cipher:\t",M
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-------"
bits = tobits(M)
print "Bits to be ciphered:",bits
u1,v1=get_uv(A,B,bits[0],q)
u2,v2=get_uv(A,B,bits[1],q)
u3,v3=get_uv(A,B,bits[2],q)
u4,v4=get_uv(A,B,bits[3],q)
print "\n------Calculation of u and v -----------------"
print "u1,v1:\t\t",u1,v1
print "u2,v2:\t\t",u2,v2
print "u3,v3:\t\t",u3,v3
print "u4,v4:\t\t",u4,v4
print "\n------Results -----------------"
print "Result bit0 is",get_result(u1,v1,q)
print "Result bit1 is",get_result(u2,v2,q)
print "Result bit2 is",get_result(u3,v3,q)
print "Result bits is",get_result(u4,v4,q)
And here’s a presentation: