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.