This is the first post in the series: Introduction to Lattice-based Cryptography. We focus on lattices as an independent mathematical concept and its properties. However, we focus on aspects that would be useful in the study of Lattice-based Cryptography.

Throughout this series, we use 2-dimensions and 3-dimensions because they are easy to work with. In practice we use sufficiently higher dimensions.

The only prequisite to start this series is to understand the following:

• $\mathbb{R}$ represents the set of all real numbers.
• $\mathbb{Z}$ represents the set of all integers.
• $\mathbb{Q}$ represents the set of all rational numbers.
• $\mathbb{R}^n$ represents the set of all n-dimensional real vectors
• $\mathbb{Z}^n$ represents the set of all n-dimensional integer vectors

What is a Lattice?

A Lattice $L$ is an infinite set of vectors $\mathbf{v}$ constructed based two condition: discreteness and additivity.

Formally, an $n$-dimensional lattice $L$ is a discrete additive subgroup of $\mathbb{R}^n$ generated by a basis $B = {b_1, b_2, …, b_n}$ as an integer linear combination: $$L = L(B):= {\sum_{i = 1}^{n}z_ib_i: z_i \in \mathbb{Z}}$$

where $z_i$ is an arbitrary integer $\mathbb{Z}$

• discrete: This means that every vector point $\mathbf{v} \in L$ has some “neighborhood” in which $\mathbf{v}$ is the only lattice point. Loosely speaking, this means that, for every point $\mathbf{v}$ there is “good space” around it. By using an integer linear combination and not just linear combination we have achieve reasonable discreteness between vector points. This is shown below using rationals $\mathbb{Q}$ as a counter example.
• additive subgroup: a lattice $L$ is an additive subgroup if it contains identity element $0 \in \mathbb{R}^n$(the zero vector), and if for any $\mathbf{v}, \mathbf{w} \in L$, we have $-\mathbf{v}, -\mathbf{w} \in L$ and $\mathbf{v} + \mathbf{w} \in L$

Below, we will see what a lattice is and what it is not.

• The singleton set ${0} \in \mathbb{R}^n$ is a lattice $L$(for any positive integer $n$). That is, the zero vector in any dimension is a lattice.

• The integers $\mathbb{Z} \in \mathbb{R}$ form a 1-dimensional lattice $L$.

• The integer grid $\mathbb{Z}^n \in \mathbb{R}^n$ is an n-dimensional lattice

• The set ${x ∈ \mathbb{Z}^n : \sum_{i=1}^nx_i ∈ 2\mathbb{Z}}$ is a lattice; it is often called the “checkerboard” or “chessboard” lattice, especially in two dimensions. It contains all $n$-vectors of integers $x = (x_1, x_2,…,x_n) \in \mathbb{Z}$ such that the sum of the components of $x$, i.e $\sum_{i = 1}^{x_i}$, is an even integer. That is, the sum of elements in the vector is an even integer.

  The opposite is not true. That is ${x ∈ \mathbb{Z}^n : \sum_{i=1}^nx_i ∈ 2\mathbb{Z} + 1}$ is not a lattice. Although it is discrete, it is not an additive subgroup of $\mathbb{R}^n$ mainly because it doesn’t contain the identity element $0 \in \mathbb{R}^n$(the all-zeros vector) as shown in non-example diagram below. Recall, that a lattice $L$ is an additive subgroup if it contains identity element $0 \in \mathbb{R}^n$, and if any $\mathbf{v}, \mathbf{w} \in L$, we have $-\mathbf{v}, -\mathbf{w} \in L$ and $\mathbf{v} + \mathbf{w} \in L$.

  Example: $(0,0),(1,1),(2,4),(−3,5),(−2,−2)$

  Non-example(opposite): $(1,0),(2,3),(−1,2)$

• Example 1: Just even integers

• Example 2: random 2-tuples and 3-tuples with sum of even integer

• Non-example: random 2-tuples and 3-tuples with sum of odd integer

• The rationals $\mathbb{Q} \subset \mathbb{R}$ do not form a lattice, because although they form a subgroup, it is not discrete: there exist rational numbers that are arbitrarily close to zero.

  For two arbitrary rational numbers $r_1$ and $r_2$, where $r_1 \lt r_2$ there are inifinitely many rational numbers between them therefore making it impossible for either $r_1$ and $r_2$ to be discrete.

  For example, below is a graph of points in $\mathbb{Q}$ between 1 and 2.

• The odd integers $2\mathbb{Z} + 1$ do not form a lattice, because although they are discrete, they do not form a subgroup of $\mathbb{R}$.

  The odd integers $2\mathbb{Z} + 1$ do not contain 0

Basis

A basis $B = {b_1, b_2, …, b_n} \subset \mathbb{R}^n$ of a lattice $L$ is a set of linearly independent vector whose integer linear combinations generate the lattice:$$L = L(B):= {\sum_{i = 1}^{n}z_ib_i: z_i \in \mathbb{Z}}$$

Recall two vectors $b_1$ and $b_2$ are said to be linearly independent if $w_i * b_1 \neq b_2$ and $w_j * b_2 \neq b_1$ where $w_i, w_j$ is an arbitrary integers.

For example, $b_1 = [1, 2, 3]$ and $b_2 = [5, 3, 7]$ are linearly independent while $b_3 = [1, 2, 3]$ and $b_4 = [2, 4, 6]$ are not. Why? $w_1 * b_3 = b_4$ and $w_2 * b_4 = b_3$ where $w_1$ and $w_2$ are $2$ and $\dfrac{1}{2}$ respectively. But, we can’t find any $w_i$ for which $w_i * b_1 = b_2$ and vice versa.

In general, the vectors $B = {b_1, b_2, …, b_n}$ are said to be linearly independent if for any vector $b_i$ in the set, it cannot be generated by the linear combination of one, some or all of the other vectors in the set. That is, $c_1b_1 + c_2b_2 + … + c_mb_m \neq b_i$ where $m$ is an arbitrary natural number.

We can also represent a basis $B$ as a matrix. This is an $n*n$ matrix where the basis vectors are the ordered columns of the matrix. This is a non-singular matrix.

With this we can represent a lattice $L = B * \mathbb{Z}^n = {Bz: z \in \mathbb{Z}^n }$

For example, given a basis $B = {b_1, b_2, b_3}$ where $b_1 = [1, 0, 0]$, $b_2 = [0, 1, 0]$ and $b_3 = [0, 0, 1]$ respectively, we have a matrix $B = \begin{bmatrix} 1 & 0 & 0\\[0.3em] 0 & 1 & 0\\[0.3em] 0 & 0 & 1 \end{bmatrix}$ and the finite set of integer vectors $z = {v_1, v_2, v_3 }$ where $v_1 = [1, 2, 5]$, $v_2 = [-5, 7, 9]$ and $v_3 = [-9, 3, 7]$ respectively, we can generate a lattice $L$ with three points $[1, 2, 5]$, $[-5, 7, 9]$ and $[-9, 3, 7]$.

This way of representing the basis is instrumental in understanding the next topic: unimodular matrix

Unimodular Matrix

Bases $B_1$, $B_2$ generate the same lattice $L$ if and only if there exists a unimodular $U \in \mathbb{Z}^{n \times n}$ such that $B_1 = B_2U$.

An integer matrix is said to be unimodular if it determinant is $\pm1$.

This property for two bases being able to generate the same lattice $L$ is what makes lattice-based cryptography possible. We will see why this is true later in this series.

We can efficiently test whether two given matrices $B_1$, $B_2$ generate the same lattice, by checking whether $B_1^{-1}·B_2$ is unimodular.

Norms

A norm or vector norm is a generalization of what we would normally call the length or magnitude of a vector.

Recall, $||{\mathbf{v}}|| = \sqrt{v_1^2 + v_2^2 + v_3^2 + …. + v_n^2}$, the magnitude or length or size of a vector ${\mathbf{v}}$. This is a type of norm called the Euclidean norm $||\mathbf{v}||_2$.

Formally, a norm on a vector space $V$ over $\mathbb{R}$ or $\mathbb{C}$ is a function $||.||:V \to \mathbb{R}$ that satisfies the properties for all vectors $\mathbf{v}$, $\mathbf{w}$ $\in$ $V$ and all scalars $\alpha$:

1. Non-negativity: $||\mathbf{v}|| \geq 0$, and $||\mathbf{v}|| = 0 \iff \mathbf{v} = 0$

2. Homogeneity: $||\alpha \mathbf{v}|| = |\mathbf{\alpha}|||\mathbf{v}||$

3. Triangle Inequality: $||\mathbf{v} + \mathbf{w}|| \leq ||\mathbf{v}|| + ||\mathbf{w}||$

For example, the Euclidean norm for the vector $\mathbf{v} = [3, 4]$ is $||\mathbf{v}||_2 = \sqrt{3^2 + 4^2} = \sqrt{9 + 16} = \sqrt{25} = 5$.

The graphical representation is displayed below. The length of the arrow is $5$.

This graph would help us understand the next topic: $i$-th successive minimum

Other norms include the Manhattan Norm, Maximum Norm and p-norm. For now, we only care about Euclidean norms.

Successive Minimum

The Euclidean Norm $||\mathbf{v}||_2$ of any vector $\mathbf{v}$ in a lattice $L$ can be interpreted as the radius $r$ of a circle (or sphere in higher dimensions) where the origin $(0, 0)$ of the graph is the centre of the circle as shown in the diagram below.

Given a lattice $L$ and a norm(i.e. the Euclidean norm), the $i$-th successive minimum $\lambda_i(L)$ is the smallest radius $r$ such that $L$ contains at least $i$ linearly independent lattice vectors of norm at most $r$ within a ball of radius $r$ centered at the origin.

In other words, what is the smallest radius $r$ such that we can find $i$ linearly independent vectors $\mathbf{v_1}, \mathbf{v_2}, …, \mathbf{v_i}$ inside the circle(or sphere) with radius $r$? Recall, that we interpret the norm of a vector as a radius $r$ when the centre is at the origin $(0, 0)$.

For example, if we generate the vectors $\mathbf{v_1} = [4, 2]$, $\mathbf{v_2} = [-5, -5]$ and $\mathbf{v_3} = [2, 11]$ given the basis points $\mathbf{b_1} = [2, 1]$ and $\mathbf{b_2} = [1, 3]$ creating a lattice $L$, what is the 1st successive minimum $\lambda_1(L)$? Or, What is $i$-th successive minimum when $i$ is 1?

We start by finding the norm of the vectors(including the basis vectors):

• $||\mathbf{b_1}||_2 = \sqrt{2^2 + 1^2} = \sqrt{4 + 1} = \sqrt{5} = 2.24$
• $||\mathbf{b_2}||_2 = \sqrt{1^2 + 3^2} = \sqrt{1 + 9} = \sqrt{10} = 3.16$
• $||\mathbf{v_1}||_2 = \sqrt{4^2 + 2^2} = \sqrt{16 + 4} = \sqrt{20} = 4.47$
• $||\mathbf{v_2}||_2 = \sqrt{-5^2 + -5^2} = \sqrt{25 + 25} = \sqrt{50} = 7.07$
• $||\mathbf{v_3}||_2 = \sqrt{2^2 + 11^2} = \sqrt{4 + 121} = \sqrt{125} = 11.18$

The smallest norm is $2.24$ and if we draw a circle using this norm as the radius, we find the linearly independent vector $\mathbf{b_1} = [2, 1]$ within the circle. Therefore, $2.24$ is the the 1st successive minimum.

Notice how it is the closest vector to the origin. It is called the smallest nonzero vector in the lattice. Take note of this, we discuss this later in the series.

Again, what is the 2nd successive minimum? We are looking for the smallest radius(i.e norm) that creates a circle containing two linearly independent vectors.

From the computed norms, we know that the second smallest vector is $\mathbf{b_2} = [1, 3]$ with norm of $3.16$. Drawing a circle using this norm as the radius, the circle contains $\mathbf{b_1}$ and $\mathbf{b_2}$. Therefore, $3.16$ is the 2nd successive minimum.

Thirdly, what is the 3rd successive minimum?

Probably $4.47$, the third smallest norm. It turns out this is not the case. They are not linearly independent because $\mathbf{v_1}$ was generated by $b_1$ and $b_2$ therefore there are only two linearly independent vectors(i.e $\mathbf{b_1}$ and $\mathbf{b_2}$) in the circle with radius $4.47$.

How about $7.07$? The fourth smallest norm. This is still not the 3rd successive minimum for the same reason as before, $\mathbf{v_2}$ was generated by $\mathbf{b_1}$ and $\mathbf{b_2}$ therefore the circle with radius $7.07$ contains only two linearly independent vectors.

And, lastly, how about $11.18$? The largest norm. Is it the 3rd successive minimum? No, it’s not. For the same reason as before.

With this, it is safe to say the 3rd successive minimum and above does not exist because all other vectors were generated by the basis points $\mathbf{b_1}$ and $\mathbf{b_2}$.

In general, the maximum $i$ in the $i$-th successive minimum is the number of basis vectors.

It’s important to point out that a lattice $L$ might have multiple basis vectors and this is an instrumental property of lattices that makes certain types of lattice-based cryptography possible.

The goal of this material was to introduce these concepts independently; appreciating their beauty without drawing parallels to their applications in lattice-based cryptography; we will do that in the other posts in this series.

In the next post, we will be looking into Hard Problems in Lattice-Based Cryptography. See you there!