Cryptographic Lattice Geometry Note 0

Posted on In Disqus:

All info comes from this note and this course.

This note will be mainly focusing on lattice definitions.

Lattice Definition

The simplest example of lattice is $\mathbb{Z}^n = \lbrace (x_1,\dots,x_n): x_i \in \mathbb{Z} \rbrace$.

Other lattices are obtained by applying linear transformation $\pmb{B}: \pmb{x} = (x_1,\dots,x_n) \mapsto \pmb{Bx} = \sum\limits_{i =1}^n x_i \cdot b_i$.

A lattice is the set of all integer linear combinations of linearly independent basis vectors $\pmb{B} = \lbrace b_1,\dots,b_n \rbrace \subset \mathbb{R}^n$: $\mathcal{L} = \sum\limits^n_{i = 1} b_i \cdot \mathbb{Z} = \lbrace \pmb{Bx}: \pmb{x} \in \mathbb{Z}^n\rbrace$.

The same lattice has many bases $\mathcal{L} = \sum\limits^n_{i = 1} c_i \cdot \mathbb{Z}$.

A formal definition of lattice is a discrete addictive subgroup of $\mathbb{R}^n$.

Given a linear subspace $\pmb{W} \subset \mathbb{R}^n$, let $\pmb{W}^{\bot} = \lbrace \pmb{x} \in \mathbb{R}^n : \forall \pmb{y} \in \pmb{W}, \langle \pmb{x}, \pmb{y} \rangle = 0\rbrace$. Define $\pi_{\pmb{W}}: \mathbb{R}^n \to \pmb{W}$ to be the orthogonal projection into $\pmb{W}$.

Dual Lattice

We can also define a lattice via a set of modular equations. Given any matrix $\pmb{A} \in \mathbb{R}^{m\times n}$, we examine
$$
\Lambda^{\bot}(\pmb{A}) = \lbrace \pmb{x} \in \text{rowspan}(\pmb{A}): \pmb{Ax\equiv 0}\pmod1 \rbrace
$$

The above is in fact equivalent to $\pmb{Ax} \in \mathbb{Z}^n$.

The condition $\pmb{x} \in \text{rowspan}(\pmb{A})$ is imposed to disallow non-zero vectors in kernel of $\pmb{A}$. If so, then we will have an entire line through the origin, and hence not discrete.

$\text{rowspan}(\pmb{A})$ means the linear subspace with basis of each row of $\pmb{A}$. Noticing that orthogonal component of kernel is equal to row space by
$$
\begin{pmatrix}
\pmb{a_1} \newline \pmb{a_2} \newline \dots \newline \pmb{a_n}
\end{pmatrix} \pmb{x} = \begin{pmatrix}
\langle \pmb{a_1}^\top, \pmb{x} \rangle \newline \langle \pmb{a_2}^\top, \pmb{x} \rangle \newline \dots \newline \langle \pmb{a_n}^\top, \pmb{x} \rangle
\end{pmatrix} =
\pmb{0}
$$
which means $\pmb{x}$ is orthonormal to every row vector $\pmb{a}_i$.

Thus if we choose an $\text{rowspan}(\pmb{A})$ element, then we avoid problems.

The most important instantion of these above is to isolate a sublattice of $\mathbb{Z}^n$ via parity check matrix.

Let $\pmb{C} \in \mathbb{Z}_p^{m\times n}$ and examine $\Lambda_p^\bot(\pmb{C}) = \lbrace \pmb{x} \in \mathbb{Z}^n: \pmb{Cx\equiv 0}\pmod p \rbrace$.

A parity check matrix lattice can be expressed in a dual lattice form. In particular, if each element in $\pmb{C}$ is integer $\lbrace 0,\dots,p-1\rbrace$, one can verify that
$$
\Lambda_p^\bot(\pmb{C}) = \Lambda^\bot\begin{pmatrix}\pmb{C}/p\newline \text{I}_n \end{pmatrix}
$$

The $\text{I}_n$ matrix at the bottom is trying to ensure each lattice $\pmb{x}$ in latter dual lattice has all integer entry.

Minimum Distance and Successive Minima

Minimum distance $\lambda_1 = \min\limits_{x,y \in \mathcal{L},x \ne y} \lVert x-y \rVert = \min\limits_{x\in \mathcal{L},x \ne 0} \lVert x\rVert$.

Successive minima $i \in \lbrack n\rbrack$: $\lambda_i = \min \lbrace r : \dim \text{ span}(\mathcal{B}(\boldsymbol{0}, r) \cap \mathcal{L}) \ge i \rbrace$.

$\mathcal{B}(\boldsymbol{0}, \cdot)$ means all the points with distance $r$ to $\boldsymbol{0}$. Thus $\mathcal{B}(\boldsymbol{0}, r) \cap \mathcal{L}$ are all the lattice points with less than $r$ distance to $\boldsymbol{0}$.

$\text{span}$ means the smallest linear subspace containing $\pmb{A} \subset \mathbb{R}^n$, where $\text{span}(\mathcal{B}(\boldsymbol{0}, r) \cap \mathcal{L})$ will be $\mathbb{R}^k$ with $k \le n$.

Thus $\lambda_i$ means the least distance where there are $i$ linearly independent lattice vectors.

For $\mathbb{Z}^n$, $\lambda_i = 1$. Always have $\lambda_1 \le \lambda_2 \le \dots\le \lambda_n$.

Let $\pmb{B} \in \mathbb{R}^{k \times n},k\ge 1$ be a non-singular matrix. Then $\lambda_1 \ge \sigma_\min(\pmb{B}) > 0$, where $\sigma_\min(\pmb{B})$ is the smallest singular value of $\pmb{B}$.

A non-singular matrix means the kernel space of matrix has only zero vector. Since unit sphere in $\mathbb{R}^n$ is compact and $\lVert \pmb{Bx} \rVert$ is continuous, $\sigma_\min(\pmb{B})> 0$ is achievable.

Also let $\pmb{x} \in \mathcal{L}(\pmb{B})$ be a non-zero vector, we express $\pmb{x = Bz}$ where $\pmb{z} \in \mathbb{Z}^n \backslash \lbrace \pmb{0}\rbrace$. By $\lVert \pmb{z}\rVert \ge 1$,
$$
\lVert x \rVert = \lVert\pmb{Bz}\rVert \ge \lVert z \rVert \sigma_\min(\pmb{B}) \ge \sigma_\min(\pmb{B})
$$

Let $\pmb{A} \in \mathbb{R}^{m \times n}$ with rows $\pmb{a_1},\dots,\pmb{a_m} \in \mathbb{R}^n$ such that $\Lambda^\bot(\pmb{A})$ is non-trivial. We have $\lambda_1(\Lambda^\bot(\pmb{A})) \ge \min \dfrac{1}{\lVert \pmb{a_i}\rVert} > 0$.

Let $\pmb{x} \in \Lambda^\bot(\pmb{A})$ be a non-zero vector, then $\exists j \in \lbrack m \rbrack, |\langle \pmb{x, a_j}\rangle | \ge 1$ since $\pmb{x} \in \text{rowspan}(\pmb{A})$.

Thus $1 \le |\langle \pmb{x, a_j}\rangle| \le \lVert \pmb{x}\rVert \Vert \pmb{a_j}\rVert \Rightarrow \lVert \pmb{x}\rVert \ge \dfrac{1}{\lVert \pmb{a_j}\rVert} \ge \min\limits_{j \in \lbrack m\rbrack} \dfrac{1}{\lVert \pmb{a}_j\rVert}$.

Shortest Non-Zero Vector

Let $\mathcal{L}$ be a non-trivial addictive subgroup of $\mathbb{R}^n$. The following are equivalent

  1. $\mathcal{L}$ is a lattice.

  2. $\lambda_1 > 0$

  3. $|\mathcal{L} \cap \mathcal{S}| < \infty$ for any bounded set $S \subseteq \mathbb{R}^n$

  4. $\mathcal{L}$ contains a shortest non-zero vector.

$1 \Rightarrow 2$. $\mathcal{L}$ is an addictive subgroup of $\mathbb{R}^n$. Also by discreteness of $\mathcal{L}$, $\pmb{0} \in \mathcal{L}$ has no immediate neighbor, thus $\lbrace \pmb{0}\rbrace$ is an open-set. Thus there exists $r > 0$ that $r \mathcal{B}^n_2 \cap \mathcal{L} = \lbrace \pmb{0}\rbrace$. $\mathcal{B}^n_2$ is unit sphere of $\mathbb{R}^n$.

Since $\mathcal{L}$ contains non-zero vector by non-trivial assumption, $\lambda_1 \ge r$ is required.

$2 \Rightarrow 3$. Let $\lambda_1 > 0, A = \mathcal{L} \cap r\mathcal{B}^n_2$. Let $\pmb{x,y} \in A, \pmb{x} \ne \pmb{y}$ and noticing that $\lVert \pmb{x} - \pmb{y}\rVert \ge \lambda_1$. Thus $(\pmb{x} + \dfrac{\lambda_1}{2}\mathcal{B}^n_2) \cap (\pmb{y} + \dfrac{\lambda_1}{2}\mathcal{B}^n_2) = \varnothing$ ($\pmb{x,y}$ with open balls of radius $\dfrac{\lambda_1}{2}$ must be interior disjoint)

If $|\mathcal{L} \cap \mathcal{S}| = \infty$, then $\pmb{x} + \dfrac{\lambda_1}{2}\mathcal{B}^n_2 \subseteq \mathcal{S} + \dfrac{\lambda_1}{2}\mathcal{B}^n_2$ and $\text{vol}_n(\mathcal{S} + \dfrac{\lambda_1}{2}\mathcal{B}^n_2) \ge \sum\limits_{\pmb{x} \in \mathcal{L}\cap\mathcal{S}}\text{vol}_n(\dfrac{\lambda_1}{2}\mathcal{B}^n_2) = \infty$. Since $\mathcal{S} + \dfrac{\lambda_1}{2}\mathcal{B}^n_2$ is bounded, then contradiction.

$3 \Rightarrow 4$. Since $\mathcal{L}$ is non-trivial, and we set $\pmb{y} \in \mathcal{L}\backslash\lbrace\pmb{0}\rbrace, r = \lVert \pmb{y}\rVert, A = (\mathcal{L} \cap r \mathcal{B}^n_2) \backslash \lbrace \pmb{0}\rbrace$. Obviously $\pmb{y} \in A$.

Since $r\mathcal{B}^n_2$ is bounded, $|A| < \infty$. We pick $\pmb{y}’ \in A$ with smallest $l_2$-norm and it is the shortest non-zero vector in $\mathcal{L}$.

$4 \Rightarrow 1$. By assumption there exists a shortest non-zero vector in $\mathcal{L}$ with length $\lambda_1$. To show $\mathcal{L}$ is discrete, we just need to prove that all the sets $\lbrace \pmb{x}\rbrace$ are open where $\pmb{x} \in \mathcal{L}$.

Taking an open ball of radius $\lambda_1$ around $\pmb{x}$. It suffices to show that the ball uniquely intersects $\mathcal{L}$ in $\pmb{x}$. If not, suppose there exists $\pmb{y} \in \mathcal{L}, \pmb{y} \ne \pmb{x}$. Then $\lVert \pmb{y}-\pmb{x}\rVert < \lambda_1$. Contradiction.

Primitive Lattice and Lattice Basis

A vector in lattice is called primitive if $\pmb{y} \in \mathcal{L}$ have $\forall t \in \mathbb{R}, t \pmb{y} \in \mathcal{L}$ if and only if $t \in \mathbb{Z}$.

Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice. A set of linearly independent vectors $\pmb{y}_1,\dots,\pmb{y}_k \in \mathcal{L}$ is primitive with respect to $\mathcal{L}$ if $\mathcal{L}(\pmb{y}_1,\dots,\pmb{y}_n) = \mathcal{L} \cap \text{span}(\pmb{y}_1,\dots,\pmb{y}_n)$.

Lemma 8

Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice. Let $\pmb{y}_1,\dots,\pmb{y}_k\in \mathcal{L}$ and $W = \text{span}(\pmb{b}_1,\dots,\pmb{b}_k)^\bot$. Then $\pi_W(\mathcal{L})$ is a lattice.

By previous shortest non-zero vector, so long as we prove that $|\mathcal{S} \cap \pi_W(\mathcal{L}) | < \infty$, where $\mathcal{S} \in \mathbb{R}^n$ is bounded, we prove $\pi_W(\mathcal{L})$ is a lattice.

We can construct an injective map $\tau: \pi_W(\mathcal{L}) \to \mathcal{L}$ satisfying $\lVert \tau(\pmb{x}) - \pmb{x} \rVert \le \sum\limits^k_{i = 1} \dfrac{1}{2} \lVert \pmb{b}_i \rVert = R$. Given such $\tau$ mapping, noticing that if $\pmb{x} \in \pi_W(\mathcal{L}) \cap \mathcal{S}$ then $\tau(\pmb{x}) \in (\mathcal{S} + R\mathcal{B}^n_2) \cap \mathcal{L}$.

By injectivity of $\tau$ and discreteness of $\mathcal{L}$ we have
$$
| \mathcal{S} \cap \pi_W(\mathcal{L}) | \le | (\mathcal{S} + R \mathcal{B}^n_2)\cap \tau(\pi_W(\mathcal{L})) | \le | (\mathcal{S} + R \mathcal{B}^n_2)\cap \mathcal{L} | < \infty
$$
To construct such $\tau$, we denote $\widehat{\pmb{x}} \in \mathcal{L}$. We have $\pi_W(\widehat{\pmb{x}}) = \pmb{x}$, where $\widehat{\pmb{x}} = \pmb{x} + \sum\limits^k_{i = 1} a_{\pmb{x}, i}\pmb{b}_i$.

Define $\tau(\pmb{x}) = \pmb{x} + \sum\limits^k_{i=1} (a_{\pmb{x}, i} - \lfloor a_{\pmb{x}, i} \rceil) \pmb{b}_i$, then we have

  • $\tau(\pmb{x}) = \widehat{\pmb{x}} - \sum\limits^k_{i=1}\lfloor a_{\pmb{x}, i}\rceil \pmb{b}_i \in \mathcal{L}$.
  • Injectivity of $\tau$ follows from $\pi_W \circ \tau \equiv 1: \pi_W(\mathcal{L}) \to \pi_W(\mathcal{L})$.
  • The distance property also follows from previous $\tau$ definition.

Lemma 9

Let $\mathcal{L} \subset \mathbb{R}^n$ be a $k$-dimensional lattice. Assume that $\pmb{b}_1,\dots,\pmb{b}_i \in \mathcal{L}$ is primitive with respect to $\mathcal{L}$ and $\widetilde{\pmb{b}_{i+1}},\dots,\widetilde{\pmb{b}_k} \in \pi_W(\mathcal{L})$ is a basis of $\pi_W(\mathcal{L})$ where $W = \text{span}(\pmb{b}_1,\dots,\pmb{b}_i)^\bot$.

Then for any choice of $\pmb{b}_{i+1},\dots,\pmb{b}_k \in \mathcal{L}$ where $\pi_W(\pmb{b_j}) = \widetilde{\pmb{b}_j}$, the vectors $\pmb{b}_1,\dots,\pmb{b}_k$ form a basis of $\mathcal{L}$.

Denote $\pmb{x}\in\mathcal{L}$, we want to prove $\pmb{x} = \sum\limits^k_{i=1} z_{\pmb{x},i}\pmb{b}_i$ with $z_{\pmb{x}, i} \in \mathbb{Z}$.

We write $\pi_W(\pmb{x}) = \sum\limits_{j = i + 1}^k z_j \widetilde{\pmb{b}_j}$ with $z_j \in \mathbb{Z}$. Now we have
$$
\pi_W(\pmb{x} - \sum^k_{j = i+1} z_j \pmb{b}_j) = \pi_W(\pmb{x}) - \sum^{k}_{j = i+1}z_j \widetilde{\pmb{b}_j} = \pmb{0}
$$
By $\pmb{x} - \sum\limits^{k}_{j = i+1}z_j \pmb{b}_j\ \bot\ \text{span}(\pmb{b}_1,\dots,\pmb{b}_i)^\bot$, we have $\pmb{x} - \sum\limits^{k}_{j = i+1}z_j \pmb{b}_j \in \text{span}(\pmb{b}_1,\dots,\pmb{b}_i) \cap \mathcal{L}$.

Since $\pmb{b}_1,\dots,\pmb{b}_i$ are primitive with respect to $\mathcal{L}$, we write $\pmb{x} - \sum\limits^{k}_{j = i+1}z_j \pmb{b}_j = \sum\limits_{j = 1}^i z_j \pmb{b}_j$.

Thus $\pmb{x} = \sum\limits^{k}_{j = 1} z_j \pmb{b}_j$, and we prove that $\mathcal{L} = \mathcal{L}(\pmb{b}_1,\dots,\pmb{b}_k)$.

Theorem 7

Let $\mathcal{L} \subset \mathbb{R}^n$ be a $k \ge 1$ dimensional lattice. $\mathcal{L}$ admits a basis of lattice vectors.

Given $\pmb{b}_1,\dots,\pmb{b}_i \in \mathcal{L}$ primitive with respect to $\mathcal{L}$, there exists $\pmb{b}_{i+1},\dots,\pmb{b}_k\in\mathcal{L}$ such that the extension $\pmb{b}_1,\dots,\pmb{b}_k$ is a basis of $\mathcal{L}$.

Trivially, we have $\mathcal{L}_1 = \mathcal{L}(\pmb{b}_1)$.

If $k \ge 2$, we let $W = \text{span}(\pmb{b}_1)^\bot$ and $\pi_W = \pi_{\text{span}(\pmb{b}_1)^\bot}$. By Lemma 8 we have $\mathcal{L}_2 = \pi_W(\mathcal{L})$ being a lattice.

Then $\mathcal{L}_2$ has dimension $k - 1$ and by induction hypothesis $\mathcal{L}_2$ admits basis $\widetilde{\pmb{b}_2},\dots,\widetilde{\pmb{b}_k}$. By construction we may choose $\pmb{b}_2,\dots,\pmb{b}_{k} \in \mathcal{L}$ such that $\pi_{\text{span}(\pmb{b}_1)^\bot}(\pmb{b}_j) = \widetilde{\pmb{b}_j}, \forall j \in \lbrack 2, k\rbrack$.

By Lemma 9, we have $\pmb{b}_1,\dots,\pmb{b}_k$ being the basis of $\mathcal{L}$.

Then we expand by setting $W = \text{span}(\pmb{b}_1,\dots,\pmb{b}_i)^\bot$ with $\pmb{b}_1,\dots,\pmb{b}_k$ being the basis of $\mathcal{L}$, trying to show any set of primitive vectors $\pmb{b}_1,\dots,\pmb{b}_i$ can be extended to a basis of $\mathcal{L}$.

Basis = Dual in Representation

If $\mathcal{L} = \mathcal{L}(\pmb{B})$ is represented in basic representation, $\pmb{B}$ is non-singular. We want to see $\mathcal{L} = \Lambda^\bot(\pmb{A})$ is expressible.

By discreteness, $\lambda_1 > 0$ in basic representation by lemma in lower bound part. The dual representation $\lambda_1 > \min \dfrac{1}{\lVert \pmb{a}_j \rVert}$ for some row $\pmb{a}_j \in \pmb{A}$.

The addictive feature simply follows from matrix multiplication.

If $\mathcal{L} = \Lambda^\bot(\pmb{A})$ is represented in dual representation, we want to have an equivalent $\mathcal{L} = \mathcal{L}(\pmb{B})$.

A very intuitive start point is: If we have a $\pmb{x} \in \Lambda^\bot(\pmb{A})$, then suppose $\pmb{x} \in \mathcal{L}(\pmb{B})$ is achievable. Then we have $\pmb{x} = \pmb{Bz}$ for some $\pmb{z} \in \mathbb{Z}^n$. We must have $\pmb{ABz} \equiv 0 \pmod 1$.

WLOG if we have $\pmb{AB} = I_k$, then any $\pmb{x}$ satisfying $\Lambda^\bot(\pmb{A})$ can be in $\mathcal{L}(\pmb{B})$.

For $\pmb{B} = (\pmb{b}_1,\dots,\pmb{b}_k)$, we admit a dual basis $\pmb{B}^\ast = (\pmb{b}^\ast_1,\dots,\pmb{b}^\ast_k)$ satisfying $\langle \pmb{b}_i, \pmb{b}^\ast_j \rangle = 1$ if $i = j$ and 0 otherwise, and $\text{span}(\pmb{B}) = \text{span}(\pmb{B}^\ast)$. Then we claim $\mathcal{L}(\pmb{B}) = \Lambda^\bot(\pmb{B}^{\ast\top})$.

  1. $\forall \pmb{x} \in \mathcal{L}(\pmb{B}), \pmb{x} \in \Lambda^\bot(\pmb{A})$. Trivially, $\pmb{B}^{\ast\top} \pmb{B} = I_k$. Then $\pmb{B}^{\ast\top} \pmb{x} = \pmb{B}^{\ast\top} \pmb{Bz} = I_k\pmb{z} = \pmb{z}$.

  2. $\forall \pmb{x} \in \Lambda^\bot(\pmb{A}), \pmb{x} \in \mathcal{L}(\pmb{B})$. By construction, $\pmb{x} \in \text{rowspan}(\pmb{B}^{\ast\top}) = \text{span}(\pmb{B}) = \text{span}(\pmb{B}^\ast)$, $\pmb{x}$ cannot be in kernel space of $\pmb{B}^{\ast\top}$.

    $\pmb{B}\pmb{B}^{\ast\top}\pmb{x} = \pmb{x}’$, we want to have $\pmb{x} = \pmb{x}’$. First, $\pmb{Bz = 0}$ if $\pmb{z = 0}$ by $\pmb{B}$ being non-singular. $\pmb{B}^{\ast\top} \pmb{x = 0}$ if and only if $\pmb{x = 0}$ by $\pmb{x} \in \text{span}(\pmb{B}^\ast)$.

    Since $\pmb{x},\pmb{x}’ \in \text{span}(\pmb{B})$, then we only have $\pmb{x = x}’$.

Equivalent Lattice Bases and Unimodular Matrix

A matrix $U \in \mathbb{Z}^{n \times n}$ is unimodular if $\det{U} = \pm 1$. Thus $U \in \mathbb{Z}^{n \times n}$ is unimodular iff $U^{-1} \in \mathbb{Z}^{n \times n}$.

$U \in \mathbb{Z^{n \times n}}$ unimodular $\Rightarrow U^{-1} \in \mathbb{Z}^{n \times n}$. By Cramer’s Rule we have $U^{-1}$ and by $\det$ of integer matrix, $U^{-1} \in \mathbb{Z}^{n\times n}$.

$U \in \mathbb{Z^{n \times n}}$ unimodular $\Leftarrow U^{-1} \in \mathbb{Z}^{n \times n}$. Trivial.

For non-singular matrices $\pmb{B}_1,\pmb{B}_2 \in \mathbb{R}^{n \times k}, \mathcal{L}(\pmb{B}_1) = \mathcal{L}(\pmb{B}_2)$ if and only if $\pmb{B}_1 = \pmb{B}_2U$ for some unimodular matrix $U \in \mathbb{Z}^{k \times k}$.

Assume that $\mathcal{L}(\pmb{B}_1) = \mathcal{L}(\pmb{B}_2)$. Then we need to prove $\mathcal{L}(\pmb{B}_1) \subseteq \mathcal{L}(\pmb{B}_2)$ and $\mathcal{L}(\pmb{B}_2) \subseteq \mathcal{L}(\pmb{B}_1)$.

Suppose $\pmb{B}_1 = \pmb{B}_2 V$ and $\pmb{B}_2 = \pmb{B}_1 K$. Then $VK = I$. Since $V, K \in \mathbb{Z}^{k \times k}$, then it must follow that $K = V^{-1}$ with $K$ unimodular matrix.