Definition: Ideal lattices

✍️ Written on 2020-06-12 in 532 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 [1], they extended the Learning With Error (LWE) problem to a so-called ring-LWE problem. Its difficulty to solve it defines the security of several candidates of the NIST post-quantum cryptography competition. In the same paper, they established the notion of ideal lattices (section 1.3) as compared to generic lattices. This article just elaborates on the definition.

I assume knowledge of basic algebra here.

[1] 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.

Preliminaries

Ring

A nonempty set R with two closed operations + and · is called ring (with multiplicative identity) if

R1

(R, +) is an Abelian group

R2

(R, ·) is a semi-group with neutral element 1_R ∈ R

R3

∀ x, y, z ∈ R: x · (y + z) = (x · y) + (x · z) ∧ (y + z) · x = (y · x) + (z · x)

Ideal

An ideal I in a ring R is an additive subgroup of R that is closed under multiplication by R. Hence subset I ⊆ R is called “ideal of R” if

I1

(I, +) is a subgroup of (R, +)

I2

∀ a ∈ I ∀ r ∈ R: ar ∈ I and ra ∈ I

Isomorphism

An isomorphism is a map σ: X → Y such that ∀ y ∈ Y ∃! x ∈ X: σ(x) = y ∧ ∀ x ∈ X ∃! y ∈ Y: σ(x) = y. Two sets X and Y are isomorphic if there exists some isomorphism σ: X → Y.

Group isomorphism

A group isomorphism is an isomorphism φ: X → Y such that (X, +) and (Y, ×) are groups and φ satisfies φ(a + b) = φ(a) × φ(b). Two groups (X, +) and (Y, ×) are isomorphic if there exists some group isomorphism.

Lattice

A lattice in ℝⁿ is a subgroup of the additive group ℝⁿ which is isomorphic to the additive group ℤₙ, and which spans the real vector space ℝⁿ.

Ideal lattices

Let R be a ring such that (R, +) is isomorphic to (ℤⁿ, +). Let σ: (R, +) → (σ®, ×) where σ® is some lattice in an n-dimensional real vector space. Then some ideal lattice is σ(I) such that I is an ideal in R.