# Part 1: Basics of Lattice Theory | A Guide to Fully Homomorphic Encryption (FHE)

## A smooth introduction to lattice theory

Hello everyone! Welcome to the first post of the fully homomorphic encryption series. In this series, we will start with the basics of lattice theory, then move on to lattice-based cryptography, and finally dive into the fundamentals of fully homomorphic encryption.

# Contents

Back to Linear Algebra

Vector Spaces

Bases

Linear Independence

Span

Fundamentals of Lattice Theory

Definition and Properties

Determinant and Volume

SVP & CVP

The Shortest Vector Problem

The Closest Vector Problem

Conclusion

# Back to Linear Algebra

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

## Vector Spaces

We want to formalize the notion of a 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 \(\mathbb{F}\) be a field. Let \(V\) be a set, a binary operation \(+\) on \(V\), and a map \(\cdot\) from \(F \times V \rightarrow V\) such that the following axioms hold:

\(v + w = w + v; \ \forall v,w \in V,\)

\(u + (v + w) = (u + v) + w; \ \forall u, v, w \in V\),

\(\exists \vec{0} \in V\) s.t. \(\vec{0} + v = v; \forall v \in V\),

\(\forall v \in V, \exists-v \in V\) s.t. \(v + (-v) = \vec{0}\),

\(\forall v \in V, 1_{\mathbb{F}} \cdot v = v\),

\(\forall a, b \in \mathbb{F}, \forall v \in V; (a + b) \cdot v = (a \cdot v) + (b \cdot v)\),

\(\forall a \in \mathbb{F}, \forall v, w \in V; a \cdot (v + w) = (a \cdot v) + (a \cdot w)\),

\(\forall a, b \in \mathbb{F}, \forall v \in V; (a \cdot b) \cdot v = a \cdot (b \cdot v)\).

\((V, + , \cdot)\) triple is called a **vector space over**\(\mathbb{F}\) if it satisfied 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.

Both scalar multiplication over vector addition and vector addition over hold.

Axioms (1)-(4) imply that \((V, +)\) is an abelian group.

### Examples

\((\mathbb{R}^n, +, \cdot)\) is a vector space over the field \(\mathbb{R}\) for all 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 \(\mathbb{F}\). Say \(v_1, v_2, ..., v_n \in V\) and \(c_1, c_2, ..., c_n \in \mathbb{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 \(v_1, v_2, ..., v_n\).

**Definition:** Let \(V\) be a vector space over \(\mathbb{F}\) and \(S\) a non-empty subset of \(V\). Then, \(S\) is called **linearly independent** if for any distinct \(v_1, v_2, ..., v_n \in S\)

$$c_1 \cdot v_1 + c_2 \cdot v_2 \ + ... + \ c_n \cdot v_n = \vec{0} \ \implies \ c_1 = c_1 = ... = c_n = 0.$$

## Span

Let \(V\) be a vector space over \(\mathbb{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 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.\)

For example, let us consider the vector space \(V = \mathbb{R}^2\) with the field \(\mathbb{F} = \mathbb{R}\) and claim that \(S = \{ (1, 0), (0, 1) \}\) is a basis, or not.

#### Proof:

**Linear Independence**

Suppose \(c_1 \cdot (1, 0) + c_2 \cdot (0, 1) = \vec{0} = (0, 0)\). Then \((c_1, c_2) = (0, 0)\). Hence \(c_1 = c_2 = 0\). So \(S\) is linearly independent.

**Span**

The fact that \(Span(S) \subset V\) is clear. So it is enough to show that \(V \subset Span(S)\). Take \(v \in V = (x, y)\). It can be rewritten in terms of a linear combination of \(S\): \(v = x \cdot (1, 0) + y \cdot (0, 1) \in Span(S)\).

Hence, \(S\) is a basis for \(\mathbb{R}^2.\)

# Fundamentals of Lattice Theory

## Definition and Properties

**Definition:** Let \(v_1, v_2, ..., v_n \in \mathbb{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 \(v_1, v_2, ..., v_n.\) 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.Notice that \((L, +) < (\mathbb{Z}^n, +)\) and \((L, +) \cong (\mathbb{Z}^n, +).\)

If the coordinates are also integers, then we call them

**integer lattices**, or**integral lattices.**

**Definition:** A matrix \(A \in \mathbb{Z}^{n \times n}\) is **unimodular** if it has a multiplicative inverse in \(\mathbb{Z}^{n \times n}.\)

**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 a 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 }.$$

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 \(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 \in L(B)\) such that \(\forall w \in L(B)\) it satisfies

$$||v - t|| = ||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.

I'm 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.