Lattices of Cryptography — Basic Results

This post is a grab bag of basic definitions and elementary results related to unstructured lattices. See ¹ for a more condensed version of similar topics or ² for a more detailed and advanced algebraic treatment.

Basis Independent Characterization

A lattice $\L$ is a discrete additive subgroup of $\RR^n$, that is,

1. $\L$ inherits the additive group structure of $\RR^n$,
2. $\L$ is equipped with a notion of distance, (or equivalently, a inner product $\braket{\cdot, \cdot} : \L\times \L \mapsto \RR$), and
3. there exits a fixed non-zero radius $\epsilon$ (see Fig. 1), such that the open ball $$\mathbb{B}(\vec{x}, \epsilon) := \lrbraces{ y \in \RR^n \; :\; \norm{x - y} < \epsilon }$$ centered at $\vec{x} \in \L$, contains no other elements of $\L$, i.e., $$ \begin{equation} \exists \epsilon > 0,\; \forall \vec{x} \in \L:\quad \mathbb{B}(\vec{x}, \epsilon) \cap \L = \{ \vec{x} \}. \label{basis-free-defn} \end{equation} $$

Since $\L$ is an additive subgroup of $\RR^n$, translations of $\L$ by an arbitrary vector $\vec{v} \in \RR^n$ forms the usual equivalence class of cosets defined by $$[\vec{v}] := \vec{v} + \L = \left \lbrace \vec{v} + \vec{x}\;:\; \vec{x} \in \L \right \rbrace \in \RR^n/\L.$$

By definition, two arbitrary vectors $\vec{x}, \vec{y} \in \RR^n$ belong to the same coset, if and only if $\vec{x} - \vec{y} \in \L$. Any set $\hatP \subset \RR^n$ that contains exactly one representative element $\vec{v}$ from each coset $[\vec{v}] \in \RR^n/\L $ is called a strict fundamental domain of $\L$, and is defined as

$$ \begin{equation} \hatP := \bigcup_{[\vec{v}] \;\in\;\RR^n/\L} \vec{v}. \label{eq:strict-fundamental-domain} \end{equation} $$

Since the choice of representative $\vec{v} \in [\vec{v}]$ is arbitrary, $\hatP$ is not uniquely determined. However, $\RR^n/\L$ partitions $\RR^n$ into its cosets, therefore translations of any given $\hatP$ by the lattice vectors tiles the entire $\RR^n$ without overlap, i.e.,

$$ \begin{aligned}\bigcup_{\vec{x} \in \L} \left (\hatP + \vec{x}\right) &= \RR^n \quad \text{and }\\ \forall\, \vec{x}, \vec{y} \in \L,\;\vec{x} \neq \vec{y}:\quad \left (\hatP + \vec{x}\right) \bigcap \left(\hatP + \vec{y}\right) &= \emptyset. \end{aligned} $$

The covolume (sometimes also called volume) is the volume of any of its strict fundamental domains (i.e., a measure of its size). For any translation invariant measure, like the Lebesgue measure, the covolume is independent of the choice of representatives used to define $\hatP$.

Basis Dependent Characterization

The characterization of a lattice so far has been entirely basis independent. This is ideal for exploring algebraic and topological properties of lattices, however, it’s not very useful for computational purposes. For that, the following basis dependent characterization is more suitable.

Since $\lbrace \vec{b}_i \rbrace$s are linearly independent, its convenient to treat them as basis vectors of $\L$ and represent them as columns of a matrix $$\B := \begin{pmatrix} \vert & & \vert \\ \vec{a}_1 & \cdots & \vec{a}_m \\ \vert & & \vert\end{pmatrix} \in \RR^{n\times m}.$$

A few additional definitions are listed below, which should largely be familiar to most readers:

When do two bases $\B_1$ and $\B_2$ generate the same lattice? The following theorem characterizes this precisely:

Integer matrices whose inverse also happen to be an integer matrix have a special name:

Since the determinant of $\U$ is $\pm 1$, and the $(i,j)$-th cofactor entry of an integer matrix is always an integer, inverse of $\U$ exists and has integer entries, that is, $\U^{-1} \in \ZZ^{m\times m}$. Furthermore, if $\U$ and $\V$ are unimodular and have the same dimension, then so is $\U\cdot \V$ because $\det(\U\cdot \V) = \det(\U)\det(\V) = \pm 1.$

To summarize, unimodular matrices form a group under usual matrix multiplication. This group is called General Linear Group over integers and is denoted by $\mathrm{GL}_m(\ZZ)$. Unimodular matrices whose determinant is $+1$ forms a subgroup of $\mathrm{GL}_m(\ZZ)$ called the Special Linear Group over integers and is denoted by $\mathrm{SL}_m(\ZZ)$.

Fundamental Parallelepiped

Rank and dimension are crude invariants of a lattice. A more fine-grained invariant is the covolume of a fundamental parallelepiped, which is defined next.

Same lattice with different bases and distinctly shaped parallelepiped.

In Fig. 1, the region shaded in green is the fundamental parallelepiped associated with the basis vectors $\B_1 := \lbrace \vec{a}_1, \vec{a}_2\rbrace$. Similarly, the region shaded in purple is also the fundamental parallelepiped, albeit associated with $\B_2 := \lbrace \vec{b}_1, \vec{b}_2\rbrace$. So, even though a lattice is independent of its basis, the shape of a fundamental parallelepiped is not.

However, in spite of this superficial difference, the fundamental parallelepiped for any basis $\B$ has two remarkable properties:

1. $\P(\B)$ does not contain any non-zero lattice point, and
2. The covolume of $\L$ is independent of the choice of the basis.

The next two lemmas make these observations precise:

Note: For the previous lemma to hold, it’s crucial that $\vec{c}_i$s are a priori known to be elements of $\L$. If $\C$ is any arbitrary linearly independent set in $\RR^n$ that satisfies $\P(\C) \cap \L = \lbrace \vec{0} \rbrace$, then such a $\C$ will not form a basis of $\L$.

The most remarkable property of a fundamental parallelepiped is that its covolume is independent of the choice of the basis.

Notice that by construction, the fundamental parallelepiped $\P(\B)$ is also a strict fundamental domain $\hatP$ \eqref{eq:strict-fundamental-domain} whose the coset representatives form a connected convex set. $\P(\B)$ is connected because the half-open unit interval $[0,1)$ is connected. It’s convex because if $\vec{x}$ and $\vec{y}$ are elements of $\P(\B)$, then $$\forall\,\highlight{t}\in [0,1] \subseteq \RR:\; \highlight{t}\cdot \vec{x} + (\highlight{1-t})\cdot \vec{y} \in \P(\B).$$

Length of Lattice Vectors

Since lattice points form a repeated pattern in $\RR^n$, each lattice vector $\vec{x} \in \L$ can be collected into an $n$-dimensional spherical shell, where each shell contains vectors of the same length. Let $\mathcal{S}_j \subseteq \L$ denote the $j$-th shell and $\nu_j$ be its radius. Assuming the index $j$ is chosen such that $\nu_0 = 0$ and $\nu_{j-1} < \nu_j$ then, the following strict ordering of $\nu_j$s is a lattice invariant:

$$\nu_0 \lt \cdots \lt \nu_{j-1} \lt \nu_j \lt \nu_{j+1} \lt \cdots \lt \infty.$$

For all lattices, $\mathcal{S}_0 = \lbrace \vec{0} \rbrace$ and is called the trivial or zero shell and $\mathcal{S}_j$ for $j>0$ is called non-trivial or non-zero shell.

Given this setup, there are three natural computational questions one can ask. (See also the aside on bounds of $\mathcal{S}_j$.)

1. Given an index $j$, and a lattice $\L(\B)$ specified by an integral basis $\B \in \ZZ^{n\times m}$, find an element of $\mathcal{S}_j$. For example, when $j=0$ it’s trivial to find an element of $\mathcal{S}_0$, since $\mathcal{S}_0 = \lbrace \vec{0}\rbrace$. But what about finding an element of $\mathcal{S}_1$ or $\mathcal{S}_{13}$? Does the difficulty depend upon the index $j$? Does it depend on the choice of $\B$?
2. Given $j$ and $\L(\B)$ as before, compute the value of $\nu_j$. Here, the problem is not to explicitly find a lattice vector but to only compute the radius $\nu_j$. Indeed, if one can find an element $\vec{x} \in \mathcal{S}_j$, then one can trivially compute $\nu_j = \abs{\vec{x}}$. However, there might be other “short cuts” that directly computes $\nu_j$ without ever explicitly finding an element of $\mathcal{S}_j$.
3. Given a lattice vector $\vec{x} \in \L(\B)$ find its position $j$ in the partial order, i.e., find $j$ such that $\abs{\vec{x}} = \nu_j.$

When the rank of $\L$ is large, solving any of these three problems is computationally challenging. Cryptographically, however, the most relevant problem is to find an element of $\mathcal{S}_1$ — which is also called the shortest vector problem. Surprisingly, it is not only hard to find a non-zero shortest vector, but also hard to find even an “approximately short” vector in $\L$.

The next few subsections make these notions precise.

Shortest Vector Problem

The Shortest Vector Problem ($\svp$) is one of the most important computational problem in lattice based cryptography. It corresponds to finding an element of $\mathcal{S}_1$, given some arbitrary basis $\B$ of the lattice.

As usual, there’s an optimization version and a decisional version of this problem which are listed below:

Intuitively, it seems that solving $\svp$ should be easy because one of the basis vectors must be the shortest vector. After all, non-zero positive or negative integer multiples of each basis vector can only increase it length, so its linear combination should also just increase the length. This intuition, however, is incorrect! In fact, something quite the opposite it true: For every given lattice $\L$, there exists a basis that’s arbitrarily long. The following theorem makes this precise.

Note: This result fails for rank-$1$ lattices. To avoid repetition, the rank of $\L$ is assumed to be at least two in the proof. Also, $\vec{e}_j$ denotes the $j$-th standard basis in the proof. The significance of $\vec{e}_j$ stems from the fact that it acts as column selector from a matrix. For example, if $\A \in \RR^{p\times q}$ and $\B \in \RR^{q \times r}$ are two compatible matrices and $\C = \A\B$ then the $j$-th column of $\C := \lbrace \vec{c}_j \rbrace $ can be expressed as

$$\vec{c}_j := \A\B\cdot \vec{e}_j = \A \cdot (\B\cdot \vec{e}_j).$$

This theorem justifies the earlier remark that for computational problems, the input $\B$ to the $\svp$-solver must have its size (in bits) bounded by $\poly(n)$.

Shortest Independent Vector Problem

The shortest vector only provides “one dimensional” information about the density or sparsity of a lattice. Computationally, it’s equally interesting to know how dense the lattice is in each dimension. For example, consider the rank-$2$ lattice generated by the basis matrix

$$ \B := \begin{pmatrix} 1 & 0 \\ 0 & 2^{100} \end{pmatrix}. $$

The shortest vector in this lattice is $(1, 0)^\top$ and the next $2\cdot 2^{100}$ short vectors (i.e., elements of $\mathcal{S}_2,\cdots, \mathcal{S}_{2^{100} - 1}$) lie on the same line in the direction of $(1, 0)^\top$. While $\mathcal{S}_1$ provides crucial information about this lattice, the rest of $\mathcal{S}_j$s up to $\mathcal{S}_{2^{100}-1}$ are practically of no use.

Successive Minima

To get information about the density of the lattice in other directions, its useful to compute the length across linearly independent vectors. The successive minima of a lattice is an invariant that measures the length of shortest linearly independent vectors in the lattice. It’s denoted by $\lambda_i$ (where $\lambda_1 = \nu_1$) and defined as follows:

In the previous example, $\lambda_1 = \nu_1 = 1$ and $\lambda_2 = 2^{100}$. Notice that $\lambda_2$ is distinct from the shell radius $\nu_2$. It’s not until shell $\mathcal{S}_{2^{100}}$ that one encounters two linearly independent vectors!

There are interesting existential lower and upper bounds on the length of successive minima. I’ll cover them in some future post.

Computational Problems

We are now ready to define the search and optimization versions of Shortest Independent Vector Problem (SIVP):

A potential decisional version is not mentioned here because it’s primarily interesting in the approximation algorithm setting.

Approximately Optimal Solutions and Gap Problems

Both Exact-SVP and Exact-SIVP are known to be $\NP$-hard. (Exact-SVP under randomized reductions ⁸!) In cryptography, however, approximate solutions to an otherwise computationally hard problem can be just as effective in breaking the cryptosystem as an exact solution. It’s therefore just as important to consider approximate solutions as it is to consider exact solutions.

To understand this, consider the familiar example of factoring. There is no known polynomial time algorithm to factor $N=p\cdot q$. But suppose there were a polynomial time heuristic algorithm which on input $N$ were to output an integer $r$, which was approximately equal to $p+q$. That is, the output $r$ came with the guarantee that

$$ r < p + q < \highlight{\alpha} \cdot r;\quad \alpha > 1$$

for a large fraction of integers. Essentially, $\alpha$ measures how well the heuristic algorithm can approximate $p + q$ when it works. Can such an algorithm be useful for breaking RSA cryptosystem?

The answer to this, of course, depends upon $\alpha$. If the value of $\alpha$ is a polynomial in the bit-length of $N$, i.e., $\alpha \in \poly(\log_2 N)$, then one can _enumerate_ all integers $i$ in the range $r$ and $\alpha\cdot r$ in polynomial time and check if $\Delta := i^2 - 4N$ is a perfect square. If $\Delta$ turns out to be perfect square, then $N$ can be trivially factored. Such a heuristic algorithm will be devastating to RSA like cryptosystems if the heuristics works on a large fraction of $\log_2(N)$-bit integers!

On the other hand, if $\alpha \not\in \poly(\log_2 N)$ then one cannot possibly enumerate all values of $i \in \braces{r, \cdots, \highlight{\alpha}r}$ in polynomial time and this specific line of attack will not be fruitful. However, RSA people should still sleep with their one eye open, because nothing rules out the existence of another heuristic algorithm which on input $N$, approximates the value of some function $f(p,q)$, where the knowledge of $f(p,q)$ could speed up factoring.

In short, for cryptographic purposes, it’s not enough that finding an exact solution is infeasible, but it’s equally important that the problem be hard to approximate in polynomial time! But what does an approximate solution to $\svp$ and $\sivp$ actually mean? It’s defined (somewhat informally) below:

$\gamma$ measures how well an approximation algorithm performs compared to the optimal. Its value is a property of the algorithm itself and is independent of any lattice instance $\L(\B)$. We will use $\gamma(n)$ to emphasize how well the approximation algorithm performs as a function of the lattice dimension.

The next two sections formally state the search, and decisional versions of these approximation problems.

$\gamma$-approximate Shortest Vector Problems

As before, let $\gamma(n) \ge 1$ be an approximation factor and let $\lambda_1 = \nu_1$ be the length of the shortest non-zero vector. The search version of the approximation problem is called SVP$_\gamma$ and is defined as follows:

The decisional version of Approx-SVP$_\gamma$ is called GapSVP$_\gamma$. GapSVP$_\gamma$ asks for an algorithm to distinguish between two types of lattices:

• lattices whose shortest vectors are shorter than a threshold $r$, and
• lattices whose shortest vectors are longer than $\highlight{\gamma(n)}\cdot r$

In those cases, where the shortest vector $\lambda_1$ happens to fall between $r$ and $\gamma \cdot r$, the algorithm is allowed to output anything — including different outputs even for the same input, or not terminate at all! More formally, GapSVP$_\gamma$ if defined as follows:

$\gamma$-approximate Shortest Independent Vector Problems

The approximate and gap versions of $\sivp$ are defined analogously to $\svp$. Recall that $\lambda_i$ denotes the $i$-th successive minima of linearly independent vectors in $\L$.

The GapSIVP$_\gamma$ problem asks to distinguish between the following two cases:

• lattices whose $n$-th successive minima is smaller than a threshold $r$, and
• lattices whose $n$-th successive minima is longer than $\highlight{\gamma(n)}\cdot r$.

More formally,

Equivalence of definitions

Finally, the following theorem states and proves that the basis-independent and basis-dependent definitions of a lattice are equivalent:

Recall from \eqref{basis-free-defn} that a set $\L \subseteq \RR^n$ is discrete if there exists a ball $\mathbb{B}(\vec{x},\epsilon) \in \RR^n$ of radius $\epsilon > 0$, such that $\forall \vec{x} \in \L:\; \mathbb{B}(\vec{x},\epsilon) \cap \L = \lbrace \vec{x} \rbrace.$