Back to index

FHE Primer: Ring Learning with Errors

2023-01-09

All the fully-homomorphic Encryption (FHE) known today use Learning with Errors (LWE) and specifically Ring Learning With Errors (RLWE) as the main cryptosystem to perform homomorphic operations. We'll need to understand this a bit before diving into FHE.

Ring Learning with Errors (RLWE) is a cryptographic technique that's based on the mathematical structure of polynomials over a finite field. The technique is used to construct a trapdoor one-way function, which is a function that is easy to compute in one direction, but difficult to invert without some additional information (the trapdoor).

Polynomials over a finite field are polynomials whose coefficients are elements of a finite field. A finite field is a closed set of numbers that can do addition, subtraction, multiplication and division operations. In our example, and most of cryptography, a finite field is denoted as Z_p where p is a prime number and it means the set of integers modulo a prime number.

So for the finite field Z_7, the numbers are {0,1,2,3,4,5,6}.

There is a difference between Learning with Errors and Ring Learning with Errors but most cryptosystems focus on the latter, so I'll skip the information overload and just focus on the latter.

The RLWE Problem

Let's explain now the RLWE Problem and why does this stuff work in cryptography:

So, we're basically using s(x) as our typical private key and a(x) and b(x) as our public key.

There's a proper public key encryption system outlined here (PDF link). That paper includes a very good primer to LWE and lattices with a nice mathematical background too.

This concludes all the info we need to know for FHE. I'll just leave a small Python snippet here to do the polynomial modulo and division by x^n + 1:

# Pick some random polynomials.
# In code, we represent polynomials by their coefficients.
# So A below is actually the polynomial "4x^3 + x^2 + 11x + 10"
A = [4,1,11,10]
sA = [6,9,11,11]
eA =[0,-1,1,1]

# n is the ring degree
n=len(A)
# q is the modulo for all coefficients under the integer finite field Z_q
q=13

print (A,sA,eA)

xN_1 = [1] + [0] * (n-1) + [1]

print (xN_1)
A = numpy.floor(numpy.polydiv(A,xN_1)[1])

bA = numpy.polymul(A,sA)%q
bA = numpy.floor(numpy.polydiv(bA,xN_1)[1])

bA = numpy.polyadd(bA,eA)%q
bA = numpy.floor(numpy.polydiv(bA,xN_1)[1])
print ("Print output\n",bA)