ringlwe introduction

ringlwe.info


Practical Information about Ring based Learning with Errors Cryptography​


What is Ring Learning with Errors?


Ring Learning with Errors (RLWE) is a computational problem which is widely believed to be very difficult to solve. This problem is being used as the foundation for a new class of public key cryptosystems designed to withstand attack by a Quantum Computer. The problem is generally described in the mathematical ring formed by degree n-1 polynomials over a finite field such as the integers mod a prime number q.


The RLWE problem can be stated in two different ways. One is called the "Search" version and the other is the "Decision" version. The Search version of the problem can be stated as follows. Let:


  • ai(x) be a set of random but known polynomials from the ring of polynomials with coefficients from the integers mod q (i.e. Fq)

  • ei(x) be a set random and unknown polynomials where the coefficients are constrained to be small over the integers (i.e. less that +/- an integer b with b much less than q)

  • s(x) be a single unknown polynomial which also has small coefficients relative to the same bound, b.

  • bi(x) be the set of polynomials bi(x) = ai(x)∙s(x) + ei(x)

Given the list of polynomial pairs (ai(x), bi(x)) find the unknown polynomial s(x)


Using the same definitions, the Decision version of the problem can be stated as follows. Given a list of polynomial pairs (ai(x), bi(x)) determine whether the bi(x) polynomials were constructed as:


bi(x) = ai(x)∙s(x) + ei(x)


or were generated with random coefficients from the integer mod q.


How is the Ring Learning with Errors Problem used in Cryptography?


There are a variety of proposals for use of the RLWE problem. These include: