# 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 , 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.

 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.