Cryptographic Lattice Geometry Note 2

Posted on In Disqus:

All info comes from this note and this course.

This note will be mainly focusing on $q$-ary lattice, SIS problem and LWE assumption.

$q$-ary Lattice

We assume that $m \ge n \ge 0$ in the following parts.

A $q$-ary lattice $\Lambda$ of dimension $m$ is a lattice satisfying $q\mathbb{Z}^m \subseteq \Lambda \subseteq \mathbb{Z}^m$.

Noticing that people denote $\mathbb{Z}_q = \mathbb{Z} / q\mathbb{Z}$, where we want to express the integers modulo $q$ by excluding all the integer $x \equiv 0 \pmod q$.

One can consider that a $q$-ary lattice is a subgroup of $\mathbb{Z}^m_q$ (or linear code of $\mathbb{Z}^m_q$) both algebraically and computationally.

Parity Check Lattice (Dual Lattice) is defined as follows: Let $\pmb{A} \in \mathbb{Z}^{n \times m}_q$ and define
$$
\begin{aligned}
\Lambda_q^\bot (\pmb{A}) &= \lbrace \pmb{x} \in \mathbb{Z}^m \mid \pmb{Ax} \equiv \pmb{0} \pmod q \rbrace \newline
&= \ker(\pmb{A}: \mathbb{Z}^m_q \mapsto \mathbb{Z}^n_q)
\end{aligned}
$$
Row-Generated Lattice is defined as follows: Let $\pmb{A} \in \mathbb{Z}^{n \times m}_q$ and define
$$
\begin{aligned}
\Lambda_q(\pmb{A}) &= \lbrace \pmb{y} \in \mathbb{Z}^m \mid \exists \pmb{s} \in \mathbb{Z}^n, \pmb{y} \equiv \pmb{As} \pmod q \rbrace \newline
&= \pmb{A}\mathbb{Z}^n + q\mathbb{Z}^m
\end{aligned}
$$
For $\pmb{A} \in \mathbb{Z}^{n\times m}_q$ and $\pmb{A}’ \in \mathbb{Z}^{m \times n}_q$, we have

  • $\dim \Lambda^\bot_q(\pmb{A}) = m, \dim\Lambda_q(\pmb{A}’) = m$.
  • $\det(\Lambda^\bot_q(\pmb{A})) \le q^n$ and $\det(\Lambda_q(\pmb{A}’)) \ge q^{m - n}$.
  • If $q$ is prime and $\pmb{A,A’}$ are non-singular in finite field $\mathbb{Z}_q$, the inequalities are equalities.

Noticing that $q\mathbb{Z}^m \subseteq \Lambda \subseteq \mathbb{Z}^m$, the dimension argument holds.

Since $\Lambda^\bot_q(\pmb{A}) = \ker(\pmb{A}), \Lambda_q^\bot(\pmb{A}) \subset \mathbb{Z}^m$ and $\det(\Lambda^\bot_q) = |\mathbb{Z}^m / \Lambda_q^\bot(\pmb{A}) |$. We noticing that $\det(\Lambda_q^\bot) = |\text{im}(\pmb{A})|$ and we argue that the image space $\text{im}(\pmb{A}) \subset \mathbb{Z}^n_q$.

Similarly, $\det(\Lambda_q(\pmb{A}’)) = | \mathbb{Z}^m / \Lambda_q(\pmb{A}’) |$. Noticing that $\text{im}(\pmb{A}’) \subset \mathbb{Z}^n_q$, then $\det(\Lambda_q(\pmb{A}’) \ge q^{m-n}$.

Let $q$ be a prime, and let $\pmb{A}\in\mathbb{Z}^{n \times m}_q$, then

  1. $\lambda_1^\infty(\Lambda_q^\bot(\pmb{A})) \le q^{n / m}$.
  2. $\lambda_1^\infty(\Lambda^\bot_q(\pmb{A})) > \dfrac{(q / 2)^{n / m} - 1}{2}$ except with probability at most $2^{-n}$ over $\pmb{A}\overset{R}{\leftarrow}\mathbb{Z}^{n \times m}_q$.

By the fact that any convex symmetric set with volume $\text{vol}_n(K) > 2^n\det(\mathcal{L})$ contains a non-zero lattice vector, we have
$$
(2 \cdot \lambda^\infty_1(\Lambda_q^\bot(\pmb{A})))^m \le 2^m \cdot \det(\Lambda^\bot_q(\pmb{A})) \le 2^m \cdot q^n
$$
Thus $\lambda_1^\infty (\Lambda^\bot_q(\pmb{A})) \le q^{n /m}$.

Recall SIS problem, where $\pmb{A}$ is a universal hash function, then $\Pr\lbrack H(\text{pk},x) = H(\text{pk},x^\ast)\rbrack = \dfrac{1}{q^n}$, i.e., it must be uniformly random distributed.

Then denote $\beta = \dfrac{(q / 2)^{n / m} - 1}{2}$ and take vectors of $l_\infty$ smaller than $\beta$, we have
$$
|\lbrace \pmb{x} \in \mathbb{Z}^m \mid \lVert \pmb{x} \rVert_\infty \le \beta \rbrace | = (2\beta + 1)^m
$$
Thus by a union bound
$$
\Pr_{\pmb{A}}\lbrack \exists \pmb{x}, \lVert \pmb{x} \rVert _\infty \le \beta, \pmb{Ax}\equiv \pmb{0}\pmod q\rbrack \le (2\beta + 1)^m q^{-n} = 2^{-n}
$$