Definition: ring-LWE

✍️ Written on 2020-06-26 in 1155 words.
Part of cs IT-security pqcrypto

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) ∈ Rq 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) ∈ Rq × Rq, where each a is uniformly random, and each product a · s is perturbed by a term drawn independently from the error distribution over R.

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® → F. Here Frac® 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

  1. (M, +) is an Abelian group.

  2. ·: R × M → M satisfies ∀ r, s ∈ R ∀ x, y ∈ M:

    1. r · (x + y) = r · x + r · y

    2. (r + s) · x = r · x + s · x

    3. (rs) · x = r · (s · x)

    4. 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 = Ok

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 As,ψ over R/qR × Kℝ/R∨ with s ∈ R∨/qR∨ and ψ ∈ Ψ is defined as

  1. Sample a as element of uniformly random element of Rq

  2. Sample e as element of error distribution ψ

  3. 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 As,ψ, find s.

An instantiation: NewHope

symbol definition

K

I assume, ℚ[ζn] as cyclotomic field

R = Ok

ℤ[x]/(xn + 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

Paper citations

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.