Summary

Learning With Errors (LWE) is a robust cryptographic method that can be used for homomorphic encryption, providing a quantum-resistant alternative to traditional encryption schemes like RSA and ECC.

Abstract

Learning With Errors (LWE) is a cryptographic technique introduced by Oded Regev in 2005, which is designed to be secure against quantum attacks. It involves creating a private key (s) and a corresponding public key based on random numbers (A) and error values (e). The public key is composed of two parts: A and B, where B is derived from A, s, and the errors e. Encryption is performed by sampling from the public key and combining the samples with the message bit (M) to produce encrypted values (u,v). Decryption is done by calculating a value (Dec) that, when less than half the prime modulus (q), indicates a zero message bit, and otherwise a one. The method can also encrypt multiple bits by ciphering each bit individually. LWE is considered a promising approach for future encryption needs, especially as it is deemed to be a strong candidate against the potential threat of quantum computing to current encryption standards.

Opinions

The author suggests that LWE is a forward-thinking approach to encryption due to its resistance to quantum attacks.
RSA and ECC are noted to be currently effective, but they may become obsolete due to high CPU utilization and potential vulnerabilities to quantum computing.
LWE is presented as part of a "new wave" in cryptography, hinting at its potential to replace or supplement existing encryption methods.
The use of Ring-LWE, a variant of LWE, is highlighted as a significant advancement, particularly as it has been adopted by Google for new cryptographic methods.
The article implies that the transition to post-quantum cryptography, with LWE as a strong candidate, is inevitable and necessary for future security.

Public Key Encryption with Learning With Errors (LWE)

Learning With Errors (LWE) is a quantum robust method of cryptography and which can also be used for homomorphic encryption. 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.

It 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(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:

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

If Dec is less than q/2, the message is a zero, else it is a 1. A sample run is [here]:

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 [here]:

------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. The following is an outline of the code:

import sys
import numpy as np
import random
import math

nvals=20

B=[]
e=[]
s = 20
message = 1

q=97
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 "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(xrange(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]],"]",
	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"

An outline of this method is here:

LWE with multiple bits

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.

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 code:

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
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)

Conclusions

RSA has severed us well, but it is often too expensive in CPU utilization, and Elliptic Curve Cryptography (ECC) is doing well now in performance and security terms. But a new wave is coming, and its has RSA and ECC in its sights.