# 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:

- vector addition,
- 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:

- v + w = w + v; ∀v, w ∈ V,
- u + (v + w) = (u + v) + w; ∀u, v, w ∈ V,
- ∃0 ∈ V such that 0 + v = v; ∀v ∈ V,
- ∀v ∈ V, ∃-v ∈ V such that v + (-v) = 0,
- ∀v ∈ V, 1 • v = v,
- ∀a, b ∈ F, ∀v ∈ V; (a + b) • v = (a • v) + (b • v),
- ∀a ∈ F, ∀v, w ∈ V; a • (v + w) = (a • v) + (a • w),
- ∀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

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

### Examples

- ($R^n$, +, •) is a vector space over the field R for all positive integer values of n.
- 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

- S is linearly independent,
- 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

- The integers m and n are the
**dimension**and the**rank**of the lattice, respectively. - 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.