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:

- a
_{i}(x) be a set of random but known polynomials from the ring of polynomials with coefficients from the integers mod q (i.e. F_{q}) - e
_{i}(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.
- b
_{i}(x) be the set of polynomials b_{i}(x) = a_{i}(x)∙s(x) + e_{i}(x)

Given the list of polynomial pairs (a_{i}(x), b_{i}(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 (a_{i}(x), b_{i}(x)) determine whether the b_{i}(x) polynomials were constructed as:

b_{i}(x) = a_{i}(x)∙s(x) + e_{i}(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:

- Key Agreement (Click here for the relevant Wikipedia Article)
- Digital Signatures (Click here for the relevant Wikipedia Article)
- Cryptographic Hashing (Click here for the relevant Wikipedia Article)