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:

• 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 =  +  * (n-1) + 

print (xN_1)
A = numpy.floor(numpy.polydiv(A,xN_1))

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