# 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*(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 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 mathnvals=20B=[]

e=[]

s = 20

M = 5q=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%qdef get_result(u,v,q):

res=(v-s*u) % q

if (res>q/2):

return 1 return 0def 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",qprint "\n------Sampling Process from public key-------"

bits = tobits(M)print "Bits to be ciphered:",bitsu1,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

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,v4print "\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: