FHE Primer: Ring Learning with Errors

2023-01-09

Other posts in the series:

1. FHE (Fully Homomorphic Encryption): Introduction
2. FHE: Learning with Errors
3. FHE: The BFV Scheme

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:

• Let R = Z[x]/(x^n + 1), where

  • Z[x] just means all polynomials with integer coefficients
  • The division of Z[x] over x^n + 1 just means all polynomials are defined modulo x^n + 1: they cannot go bigger than the degree of the positive integer n. In the literature, x^n + 1 is known as the irreducible polynomial
  • We'll see some example polynomials below

• Choose a secret key s(x) randomly from the polynomial set R.

• Choose a public key a(x) randomly from polynomial set R.

• Choose an error polynomial e(x) randomly from polynomial set R.

• Assume we calculate b(x) = (a(x) * s(x)) + e(x)

• The RLWE Problem states that it is computationally infeasible to find s(x) if one was given a(x) and b(x).

• Furthermore, it is computationally infeasible to determine whether b(x) was constructed from b(x) = (a(x) * s(x)) + e(x) if one was only given b(x) and a(x) or whether it was generated randomly from the polynomial set R.

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)