Part 1: Lattice Theory | Building Blocks of FHE

This blog post is part of a series covering the foundations of FHE. In this installment, we cover lattice theory.

We revisit the key principles of linear algebra, focusing on vector spaces and their operations, such as vector addition and scalar multiplication. By understanding these foundational ideas, we can better appreciate the structure of vector spaces and how they extend into more complex constructs like lattices. This groundwork is essential for getting the fundamentals into lattice-based cryptography, where concepts like bases, linear independence, and spans play a pivotal role in defining the mathematical frameworks used to ensure data security.

Back to Linear Algebra

Linear algebra is a branch of mathematics concerning linear maps, equations, and their representations in vector spaces.

Vector Spaces

We want to formalize the notion of vector. But it is easier to formalize the notion of a set of vectors together with the operations of:

  1. vector addition,
  2. scalar multiplication.

Definition: Let F be a field, V be a set, + be a binary operation on V, and • be a map from F × V to V such that the following axioms hold:

  1. v + w = w + v; ∀v, w ∈ V,
  2. u + (v + w) = (u + v) + w; ∀u, v, w ∈ V,
  3. ∃0 ∈ V such that 0 + v = v; ∀v ∈ V,
  4. ∀v ∈ V, ∃-v ∈ V such that v + (-v) = 0,
  5. ∀v ∈ V, 1 • v = v,
  6. ∀a, b ∈ F, ∀v ∈ V; (a + b) • v = (a • v) + (b • v),
  7. ∀a ∈ F, ∀v, w ∈ V; a • (v + w) = (a • v) + (a • w),
  8. ∀a, b ∈ F, ∀v ∈ V; (a • b) • v = a • (b • v).

(V, +, •) triple is called a vector space over F if it satisfies the axioms above.

Elements of V are called vectors.

Some Remarks

  1. Vector spaces are commutative.
  2. All vector spaces have an additive identity.
  3. All vectors have inverses within the same vector space.
  4. Distributivity of scalar multiplication over vector addition holds.
  5. Axioms (1)-(4) imply that (V, +) is an abelian group.

Examples

  1. ($R^n$, +, •) is a vector space over the field R for all positive integer values of n.
  2. Set of functions from any set S to a vector space with relevant operations is a vector space.

Bases

Linear Independence

Definition:

Let V be a vector space over a field F. Say $v_1, v_2, …, v_n \in V$ and $c_1, c_2, …, c_n \in F$. An expression of the form

$$ c_1 \cdot v_1 + c_2 \cdot v_2 \ + ... + \ c_n \cdot v_n $$

is called a linear combination of the specified vectors.

Span

Let V be a vector space over F and let S be a non-empty subset of V.

Definition: The span of S is the following subset of V:

$$ Span(S) = \{ c_1 \cdot v_1 \ + ... + \ c_n \cdot v_n \ | \ \exists n; c_1, ..., c_n \in \mathbb{F}; v_1, ..., v_n \in S \}. $$

Definition: Let V be a vector space, S a subset of V. Then S is called a basis for V if

  1. S is linearly independent,
  2. Span(S) = V.

Fundamentals of Lattice Theory

Definition and Properties

Definition: Let $v_1, v_2, …, v_n \in R^m$ be a set of linearly independent vectors. The lattice L, generated by these vectors, is the set of integer linear combinations of these basis vectors. That is,

$$ L = \{ a_1v_1 \ + ... + \ a_nv_n \ | \ a_i \in \mathbb{Z} \ \forall i \}. $$

Notes

  1. The integers m and n are the dimension and the rank of the lattice, respectively.
  2. If m=n, then L is called a full-rank lattice.

Definition: An integer matrix A is unimodular if it has a multiplicative inverse in the set of n x n integer matrices.

Definition: If B and B’ are two basis matrices, then

$$ L(B) = L(B') $$

if and only if

$$ B' = AB $$

for some unimodular matrix A.

Determinant & Volume

Definition: Let L be an n-dimensional lattice with basis

$$ \{v_1, v_2, ..., v_n \}. $$

Then the fundamental domain of L is

$$ F(v_1, ..., v_n) = \{ t_1v_1 + \ ... \ t_nv_n \ | \ t_i \in [0, 1) \}. $$

Definition: Let L be an n-dimensional lattice with a fundamental domain F. Then the n-dimensional volume of F is called the determinant of L, denoted by

$$ det(L). $$

Proposition: If L is an n-dimensional full-rank lattice with a basis

$$ B = \{ v_1, ..., v_n \} $$

and an associated fundamental domain F. Then the volume of F is equal to the absolute value of determinant of the basis. That is,

$$ det(L) = Vol(F) = |det(B)|. $$

SVP & CVP

The Shortest Vector Problem

Definition: Given a lattice L, the length of the shortest non-zero vector in L which is also the minimum distance between any two lattice vectors is defined as

$$ \lambda_1(L) = min \{ ||v|| \ | \ v \in L - \{0\} \} $$

$$ \lambda_1(L) = min\{ ||x - y|| \ | \ x, y \in L; x \neq y \}. $$

where the norm is defined as

$$ ||v|| = \sqrt{<v,v>}. $$

The difficulty of SVP lies in the fact that when the dimension increases, it gets exponentially more difficult to find the shortest vector in a lattice.

The Closest Vector Problem

Definition: Given a basis B and a target vector t that is not in the lattice L(B), find a vector in L(B) that is closest to t, i.e., find a vector v ∈ L(B) such that ∀w ∈ L(B) it satisfies

$$ ||v - t|| \leq ||w - t||. $$

Similar to the SVP, the closest vector problem gets also extremely difficult as the number of dimension gets higher.

Conclusion

In this first post of our series on fully homomorphic encryption, we've discussed the foundational knowledge necessary for understanding the world of lattice-based cryptography. Starting with the essentials of linear algebra, we explored the concepts of vector spaces and bases, which are crucial for grasping the underlying principles of lattice theory.

We then delved into the fundamentals of lattice theory itself, discussing its definition, properties, and the significance of determinants and volume in the context of lattices. Additionally, we introduced two pivotal problems in lattice theory: the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP), highlighting their computational challenges and importance in cryptography.

We're aiming to make this series as pedagogical as possible for anyone with a technical background. Stay tuned for the next post where we will be discussing Learning with Errors (LWE) problem.

Subscribe to our newsletter

Top industry insights on FHE.

By clicking Sign Up you're confirming that you agree with our Terms and Conditions.
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.