fundamentals.md

fundamentals and mathematical background of lattice-based cryptography

what is a lattice?

An $n$-dimensional lattice $L$ is a discrete addictive subgroup of $\mathbb{R}^n$

• discrete: This means that every point $x \in L$ has some "neighborhood" in which $x$ is the only lattice point. That is, for every point $x$ there is "good" space around it
• addictive subgroup: a lattice $L$ is an addictive subgroup if it contains identity element $0 \in \mathbb{R}^n$(the all-zeros vector), and if any $x, y \in L$, we have $-x \in L$ and $x + y \in L$

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

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

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

• 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-tuples of integers $x = (x_1, x_2,...,x_n) \in \mathbb{Z}$ such the sum of the components of $x$, i.e $\sum_{i = 1}^{x_i}$, is an even integer.

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

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

• CASE 1: Just even integers

• CASE 2: random 2-tuples with sum of even 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}$.

  Recall, that a lattice $L$ is an addictive subgroup if it contains identity element $0 \in \mathbb{R}$(the all-zeros vector), and if any $x, y \in L$, we have $-x \in L$ and $x + y \in L$.

  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 combinatios 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 * b_1 \neq b_2$ and $w * b_2 \neq b_1$ where $w$ is an arbitrary number.

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 this case, this is generalized to vectors of $B = {b_1, b_2, ..., b_n}$ where for any two vectors in the set $B$, they are linearly independent.

We can also represent a basic $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 if lattice $L$ if and only if there exists a unimodular $U \in \mathbb{Z}^{n \times n}$ such that $B_1 = B_2U$.

This property for two bases being able to generate the same lattice $L$ increases the hardness of solving problems in lattice-based cryptography.

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.