## Motivation

Lattice-based cryptography is largely built upon the work by Vadim Lyubashevsky, Chris Peikert, and Oded Regev. In [LPR], definition 3.2 defines the ring-LWE problem we discuss here. They extended the Learning With Error (LWE) problem to a so-called ring-LWE problem. Whereas LWE requires large keys, ring-LWE overcomes this problem by defining sample a to be some ring element. It gives a basis for many instantiations as key encapsulation mechanisms like NewHope, CRYSTALS-Kyber, and Saber. For those of you, familiar with pre-quantum cryptography and new to PQCRYPTO, an analogy can be given: What integer factorization is to RSA, ring-LWE is to NewHope.

The ring-LWE problem in R, denoted R-LWE, may be informally defined as follows (the formal, more general definition is given in Section 3): fix a certain error distribution over R that is concentrated on ‘small’ elements – informally, those having small integer coefficients — and let s = s(x) ∈ R_{q}be uniformly random. Analogously to LWE, the goal is to distinguish arbitrarily many independent ‘random noisy ring equations’ from truly uniform pairs. More specifically, the noisy equations are of the form (a, b ≈ a · s) ∈ R_{q}× R_{q}, where each a is uniformly random, and each product a · s is perturbed by a term drawn independently from the error distribution over R.

[LPR] | O. Regev, “On Ideal Lattices and Learning with Errors over Rings,” in Algorithmic Number Theory, vol. 6197, G. Hanrot, F. Morain, and E. Thomé, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 3–3. |

## Prerequisites

*Number field* is an algebraic term. Essentially, you consider the rational numbers ℚ together with addition and multiplication. This defines a field (ℚ, +, ·). We can also add additional elements like the imaginary unit *i* and define addition and multiplication appropriately for it. This gives us the field (ℚ[i], +, ·). Informally, with *i* we added a finite number of elements, giving us a field extension of ℚ of finite degree. A *number field* is a finite-degree field extension of ℚ.

Let R be a commutative ring. The ring of *integral elements over A* is the set of r ∈ R that are roots of a monic polynomial (i.e. polynomial with leading coefficient 1) over a subring A of R.

A *ring of integers* of number field K is the ring of all integral elements contained in K.

An *integral domain* is a nonzero commutative ring such that the product of any nonzero elements is nonzero.

The *field of fractions R of an integral domain* is the smallest field F such that h: R → F, as an injective ring homomorphism from R into a field F, is extended by a unique ring homomorphism g: Frac(R) → F. Here Frac(R) denotes the set of all fractions e/d with e, d ∈ R with d ≠ 0. As an example, the field of fractions of the ring of integers is the field of rationals, because ℚ = {a/b | a, b ∈ ℤ and b ≠ 0}.

An *ideal* is an additive subgroup of R that is closed under multiplication by R.

Let R be a ring and 1 be its multiplicative identity. M is a *left R-module* if

- (M, +) is an Abelian group.
- ·: R × M → M satisfies ∀ r, s ∈ R ∀ x, y ∈ M:
- r · (x + y) = r · x + r · y
- (r + s) · x = r · x + s · x
- (rs) · x = r · (s · x)
- 1 · x = x

Let N be a subgroup of M. N is a *R-submodule* if ∀ n ∈ N ∀ r ∈ R: r · n ∈ N. For example (9) is an r-submodule of ℤ_{18}.

Let R be an integral domain and K be its field of fractions. A *fractional ideal* of R is an R-submodule I of K such that there exists a non-zero r ∈ R such that rI ⊆ R. For example, 5/4 · ℤ is a fractional ideal over ℤ.

The *dual fractional ideal* of I is defined as {x ∈ K | xI ⊆ R}.

## Definition

symbol | meaning |

K | number field |

R = O_{k} |
ring of integers of K |

R^{∨} |
dual (i.e. co-different) fractional ideal of R |

q | rational integer modulus with q ≥ 2 |

Ψ | family of distributions over K_{ℝ} |

The distribution A_{s,ψ} over R/qR × K_{ℝ}/R^{∨} with s ∈ R^{∨}/qR^{∨} and ψ ∈ Ψ is defined as

- Sample
*a*as element of uniformly random element of R_{q} - Sample
*e*as element of error distribution ψ - Return tuple
*a*and*(a · s) / q + e*mod R^{∨}where*(a · s) / q*∈ 1/q R^{∨}/R^{∨}and addition is done in K_{ℝ}/R^{∨}.

The search version of the ring-LWE problem is given as follows:

Given arbitrarily many, independent samples from A_{s,ψ}, find s.

## An instantiation: NewHope

symbol | definition |

K | I assume, ℚ[ζ_{n}] as cyclotomic field |

R = O_{k} |
ℤ[x]/(x^{n} + 1) for n as power of 2 |

R^{∨} |
unknown to me |

q | 12289 |

Ψ | Discrete Gaussian distribution approximated with the Hamming Weight of a pseudorandom value |