Learning With Errors and Ring Learning With Errors

Our existing public key methods are at great danger of being cracked by quantum computers. One of the methods that is proposed as a hard…

Learning With Errors and Ring Learning With Errors

Our existing public key methods are at great danger of being cracked by quantum computers. One of the methods that is proposed as a hard problem for quantum computers of Learning With Errors (LWE).

Introduction

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 (A[]) and calculate B[] = A[] x s + e. The values of A[] and B[] become our public key. If s is a single value, A and B are one dimensional matrices. If we select s to be a one-dimensional matrix, A will be a two-dimensional matrix, and B will be a one-dimensional matrix.

Learning with errors 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:

B=A×s+e

where you know A and B. The value of s becomes the secret values (or the secret key), and A and B can become the public key. Slides: [here]

In the above presentation, we use the examples defined here. The following code implements a basic LWE method:

import numpy as np
import sys
q=13
A=np.array([[4 ,1, 11, 10],[5, 5 ,9 ,5],[3, 9 ,0 ,10],[1, 3 ,3 ,2],[12, 7 ,3 ,4],[6, 5 ,11 ,4],[3, 3, 5, 0]])
sA = np.array([[6],[9],[11],[11]])
eA = np.array([[0],[-1],[1],[1],[1],[0],[-1]])
bA = np.matmul(A,sA)%q
print bA
bA = np.add(bA,eA)%q
print
print "Print output\n",bA

A demonstration of LWE is here.

Ring LWE

In the presentation defined in the video we will use the examples defined here. The following code implements a basic Ring LWE method:

A = [4,1,11,10]
sA = [6,9,11,11]
eA =[0,-1,1,1]
n=4
print A,sA,eA
xN_1 = [1] + [0] * (n-1) + [1]
print xN_1
A = np.floor(p.polydiv(A,xN_1)[1])
bA = p.polymul(A,sA)%q
bA = np.floor(p.polydiv(bA,xN_1)[1])
bA = p.polyadd(bA,eA)%q
bA = np.floor(p.polydiv(bA,xN_1)[1])
print "Print output\n",bA

The following is the example which this implements:

In this method we perform a similar method to the Diffie Hellman method, but use Ring Learning With Errors (RLWE). With RLWE we use the coefficients of polynomials and which can be added and multiplied within a finite field (Fq) [theory] and where all the coefficients will be less than q. Initially Alice and Bob agree on a complexity value of n, and which is the highest co-efficient power to be used. They then generate q which is 2n−1. All the polynomial operations will then be conducted with a modulus of q and where the largest coefficient value will be q−1. She then creates ai(x) which is a set of polynomial values:

A=an−1xn−1+…+a1x+a1x2+a0

Next Alice will divide by Φ(x), which is xn+1:

A=(an−1xn−1+…+a1x+a1x2+a0)÷(xn+1)

In Python this is achieved with:

xN_1 = [1] + [0] * (n-1) + [1]
A = np.floor(p.polydiv(A,xN_1)[1])

Alice now generates an error polynomial (e) and a secret polynomial (s):

e_A=en−1xn−1+…e2x2+e1x+e0(modq)

s_A=sn−1xn−1+…s2x2+s1x+s0(modq)

Alice now creates bA

which is a polynomial created from A, e_A and s_A:

b_A=A×sA+eA

In coding this is defined as:

bA = p.polymul(A,sA)%q
bA = np.floor(p.polydiv(sA,xN_1)[1])
bA = p.polyadd(bA,eA)%q

Bob now generates his own error polynomial e′

and a secret polynomial s′:

e_B=e′n−1xn−1+…e′2x2+e′1x+e′0(modq)

s_B=s′n−1xn−1+…s′2x2+s′1x+s′0(modq)

Alice shares A

with Bob, and Bob now creates b_B which is a polynomial created from A, e_B and s_B:

b_B=A×s_B+e_B

The code for this is:

sB = gen_poly(n,q)
eB = gen_poly(n,q)
bB = p.polymul(A,sB)%q
bB = np.floor(p.polydiv(sB,xN_1)[1])
bB = p.polyadd(bB,eB)%q

Alice then takes Bob’s value (b_B) and multiplies by s_A and divides by xn+1:

shared_A=b_B×s_A÷(xn+1)

Bob then takes Alice’s value (b_A) and multiplies by s_B and divides by xn+1:

shared_B=b_A×s_B÷(xn+1)

At the end of this, Bob and Alice will have the same shared value (and thus can create a shared key based on it).

In code this is:

sharedAlice = np.floor(p.polymul(sA,bB)%q)
sharedAlice = np.floor(p.polydiv(sharedAlice,xN_1)[1])%q 
sharedBob = np.floor(p.polymul(sB,bA)%q)
sharedBob = np.floor(p.polydiv(sharedBob,xN_1)[1])%q

A demonstration of Ring LWE is here.

Public key and 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. An example of encryption with multiple bits is given here.

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)+q2M(mod q)

The encrypted message is (u,v). To decrypt, we calculate:

Dec=v−su(mod q)

If Dec is less than q2, 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

A demonstration of LWE for public keys is here.

Homomorphic Encryption with Learning With Errors

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. In this case we will take two values and then do a bitwise ADD operation. If the values are the same, we should get a deciphered value of 0000.

For homomophic encryption, we can perform a single-bit adder function by generating (u,v) for each of the bits and then performing (for the two values for bit0 - v1_0,u1_0,v2_0 and u2_0):

Bit=(v1_0−s u1_0)+(v2_0−s u2)0)(mod q)

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:

------Parameters and keys-------
Value to cipher:	5 5
Public Key (A):	[75, 43, 2, 14, 6, 55, 7, 93, 0, 1, 41, 52, 57, 22, 64, 59, 51, 35, 27, 38]
Public Key (B):	[86, 23, 11, 73, 31, 83, 38, 78, 2, 6, 12, 69, 92, 16, 31, 7, 63, 81, 41, 94]
Errors (e):		[2, 2, 1, 3, 1, 2, 3, 1, 2, 1, 1, 3, 1, 3, 2, 3, 2, 3, 3, 1]
Secret key:		5
Prime number:		97
------Sampling Process from public key-------
Bits to be ciphered: [1, 0, 1, 0, 0, 0, 0, 0] [1, 0, 1, 0, 0, 0, 0, 0]
[11, 18, 14, 10, 2]
[18, 13, 17, 4, 0]
[3, 6, 7, 1, 4]
[11, 3, 6, 8, 7]
[10, 7, 12, 8, 11]
[4, 9, 16, 6, 7]
[0, 11, 4, 12, 14]
[10, 13, 8, 16, 9]
------Results                -----------------
Result bit0 is 0
Result bit1 is 0
Result bit2 is 0
Result bit3 is 0

A demonstration of this is here.

Conclusions

So goodbye to old public key methods? Well if quantum computers are built at scale, we may have to find alternatives, and LWE and Ring LWE are well placed for creating an alternative.