# III. Introduction of Lattice-Based Cryptography

[TOC]

## Introduction
This is the third chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. This chapter explores lattices as essential mathematical tools used across mathematics, physics, and computer science. Intuitively, a lattice resembles a vector space but is critically distinguished by consisting only of discrete vectors—elements with discrete values, as opposed to the continuous real-valued vectors found in standard vector spaces. Crucially, all currently implemented Fully Homomorphic Encryption (FHE) schemes rely on the security provided by lattice-based cryptography.

## Definitions
### 1. Lattice
Let $v_1, \dots, v_n \in \mathbb{R}^m$ be a set of linearly independent vectors. The *lattice* $L$ generated by $v_1, \dots, v_n$ is the set of integer linear combinations of $v_1, \dots, v_n$. That is,
$$L = \{a_1v_1 + \dots + a_nv_n \mid a_1, \dots, a_n \in \mathbb{Z}\}.$$
Here, the difference with vector spaces is that the coefficients in the linear combination are integers.

---
### 2. Dimension, rank
The integers $m$ and $n$ are the **dimension** and **rank** of the lattice respectively. If $m = n$, then $L$ is a **full-rank** lattice. In most cases, we work with full-rank lattices.

It follows from the definition that a lattice is closed under addition. Hence, we can say that an n-dimensional lattice is a discrete additive subgroup of $\mathbb{R}^n$. It is isomorphic to the additive group of $\mathbb{Z}^n$. That is,
$$(L, +) \cong (\mathbb{Z}^n, +) \subseteq (\mathbb{R}^n, +).$$

It is often convenient to work with lattices whose coordinates are integers. These are called **integer lattices** or **integral lattices**. For example, the set of even integers forms an integer lattice, but not the set of odd integers because it is not closed under addition.


---
### 3. Basis
A **basis** of a lattice $L$ is a set of linearly independent vectors $B = \{b_1, \dots, b_n\}$ that spans the lattice, that is,
$$L(B) = \{z_1b_1 + \dots + z_nb_n \mid z_i \in \mathbb{Z}\}.$$
For example, the vectors $\{b_1, b_2\}$ form a basis of the lattice in Figure 3.

## Hardness Problems (Assumptions)
We've covered the fundamental properties of lattices. While the field is rich with further mathematical ones, the knowledge we've gained is sufficient to dive into the core hardness problems. In this section, we briefly introduce the basic ones as follows.

### 1. Closest Vector Problem (CVP)
Given a lattice basis $B$ and a target vector $\mathbf{t}$ that is not in the lattice $L(B)$, find a vector in $L(B)$ that is closest to $\mathbf{t}$, i.e., find a vector $\mathbf{v} \in L(B)$ such that for all $w \in L(B)$ it satisfies $\|\mathbf{v} - \mathbf{t}\| \leq \|\mathbf{w} - \mathbf{t}\|$.

---
### 2. Shortest Vector Problem (SVP)
Given a lattice basis $B$, find a shortest non-zero vector in the lattice $L(B)$, i.e., find a non-zero vector $\mathbf{v} \in L(B)$ such that $\|\mathbf{v}\| = \lambda_1(L(B))$.

---
### 3. Shortest Independent Vector Problem (SIVP)
Given a lattice basis $B$ of an $n$-dimensional lattice $L(B)$, find $n$ linearly independent vectors $\mathbf{v}_1, \dots, \mathbf{v}_n \in L(B)$ such that $\max_{i \in [1, n]} \|\mathbf{v}_i\| = \lambda_n(L(B))$.

---
### 4. Short integer solution problem (SIS)
Let $\mathbf{a}_i \in \mathbb{Z}_q^n$ be a length $n$ vector with entries taken uniformly from $\mathbb{Z}_q$. Let $A = [\mathbf{a}_1 \mid \dots \mid \mathbf{a}_m]$ be an $n \times m$ matrix whose columns are $m$ linearly independent $\mathbf{a}_i$s. The SIS problem is to find a non-zero vector $\mathbf{x} \in \mathbb{Z}^m$ such that

- $\|\mathbf{x}\| \leq \beta$ and
- $A\mathbf{x} = \mathbf{0} \in \mathbb{Z}_q^n$, i.e., $x_1\mathbf{a}_1 + \dots + x_m\mathbf{a}_m = \mathbf{0} \mod q$.

Notice that the norm bound exists to ensure the problem is not easily solvable by for example Gaussian elimination. It must satisfy $\beta < q$ to avoid the trivial solution $\mathbf{x} = (q, 0, \dots, 0)$. Moreover, $\beta$ and $m$ must be large enough to allow a solution to exist.

## Conclusion
We've covered the basics of lattice-based cryptography and the general hardness assumptions that power it. But we've saved the best—and most important—for last. Currently, all modern **Fully Homomorphic Encryption (FHE)** schemes are built on one foundational problem: **Learning With Errors (LWE)** and its variants. This isn't just another assumption; it's the cornerstone of practical, post-quantum private computation. In the next post, we'll deep-dive into the LWE problem, understanding exactly why it's so powerful and how it enables truly groundbreaking technology like FHE.

## Reference
- [A Tutorial Introduction to Lattice-based Cryptography and Homomorphic Encryption](https://arxiv.org/abs/2208.08125)