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:
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.
There are a variety of proposals for use of the RLWE problem. These include: