0
$\begingroup$

A $m$-dimentional full-rank integer lattice $\Lambda\in\mathbb{Z}^{m}$ can be defined as the set of all integer linear combinations of $m$ linearly independent over $\mathbb{R}$ basis vectors $\textbf{B}=\{\vec{b}_{1},\ldots,\vec{b}_{m}\}\subset\mathbb{Z}^{m}$: $$\lambda=\mathcal{L}(\textbf{B})=\left\{\textbf{B}\vec{c}=\sum_{i=0}^{i=m} c_{i}\vec{b}_{i}:\vec{c}\in\mathbb{Z}^{m}\right\}$$

Now, we want to consider group theoretic definition of a lattice:
$m$-dimentional full-rank integer lattices $\Lambda\in\mathbb{Z}^{m}$ are discrete additive subgroups of $\mathbb{Z}^{m}$ having finite index, i.e., the quotient group $\frac{\mathbb{Z}^{m}}{\Lambda}$ (its elements are sets) is finite.
[David Cash, Dennis Hofheinz, Eike Kiltz, Chris Peikert."Bonsai Trees, or How to Delegate a Lattice Basis", In Journal Of Cryptology 2012]

Question 1: Is there any intuitive concrete example of this quotient group modulo a lattice, $\frac{\mathbb{Z}^{m}}{\Lambda}$,?

A lattice is $\color{red}{infinite}$, but lattice crypto actually uses the $\color{red}{finite\ Abelian\ group}$ $\frac{\mathbb{Z}^{m}}{\Lambda}$. It works modulo the lattice $\Lambda$.
[Phong Nguyen. "Lattice based Cryptography Slides" In Post Quantum Cryptography Winter School 2016]

Question 2: Does $\frac{\mathbb{Z}^{m}}{\Lambda}$ being a finite group has any uses in lattice cryptography (like in hardness of some problems, or in security reductions, ...)? Or it happens to $\Lambda$ has a finite index, and it's just a mathematical property (not interesting in cryptography)?

$\endgroup$

1 Answer 1

1
$\begingroup$

The finite-index property is not fundamental from a mathematical perspective. Note that not all mathematical lattices are finite-index subgroups of $\mathbb{Z}^n$. This is a property of what are called "full rank" lattices. As a trivial example, the lattice $\mathbb{Z}^{n-1}\oplus \{0\}\subseteq \mathbb{Z}^n$ has index $|\mathbb{Z}^n / \mathbb{Z}^{n-1}\oplus \{0\}|= |\mathbb{Z}| = \infty$. Often it is natural to define mathematical lattices as (non-full rank) lattices in some higher-dimensional space, see for example the definition of the Leech lattice (a rank 24 latice) in 26-dimensional Lorentzian space.

For cryptography though, the property is fundamental. In cryptography, when working with some algebraic object $G$, it is important we can encode representations of elements of $g$ in some fixed amount of space. As a trivial example, if we wanted to do cryptography over $\mathbb{Z}$, and used a variable-length encoding (say binary for simplicity), then if an adversary sees a message of length 1, they know it is either $0$ or $1$, vs a length 100 message, which is neither of these. In short, variable length encodings introduce a side-channel, which can hurt security.

Lattices $L$ are by default infinite-size objects, i.e. $|L| = \infty$. Fortunately, most lattices are periodic, in the sense that one can write

$$L = (L\bmod k) + k\mathbb{Z}^n,$$

i.e. we can split the lattice into parts that are 0 $\bmod k$, and the rest of things. It is well-known that for $L\subseteq \mathbb{Z}^n$ that is full-rank, that $k = \det L$ suffices. In practice though, $\det L$ can be exponential in $n$, so we often want to restrict to lattices that are "more periodic", i.e. there is some $q$ (that is relatively small) such that $q\mathbb{Z}^n \subseteq L\subseteq \mathbb{Z}^n$. If such a $q$ exists, we call $L$ $q$-ary.

Anyway, for $q$-ary lattices, we can work not with the (infinite) lattice $L$, but with its reduction mod $q$, which is $L/q\mathbb{Z}^n$. Here, we get a nice fixed-length encoding, as $|L/q\mathbb{Z}^n| \leq q^n$, so each lattice point is encodable in at most $n\log_2 q$ bits. For $q = \mathsf{poly}(n)$ (typical), this means we can represent lattice points with space quasi-linear in $n$.

If we removed this finite index (= full rank) property, this would no longer be true, and we would have to use a variable-length encoding to represent lattice elements, which would cause security issues. So it is more than just a mathematical coincidence.

$\endgroup$
2
  • $\begingroup$ Each paragraph was new and informative for me: Leech lattice, importance of periodicity, introducing $q$-ary lattice in this way, and the security leak. Just one question: most lattices are periodic in the sense that was written. But all of them are periodic structures that we can use some tools like Fourier transform to analyzing them, Is that true? $\endgroup$ Jun 26, 2023 at 22:46
  • 1
    $\begingroup$ All of them are periodic, I just don't have access to the precise reference for the general case. I think for full-rank $L\subseteq \mathbb{R}^n$, we get something like $(\det L)^2 \mathbb{Z}^n\subseteq L$, i.e. these are still periodic in the sense I mentioned (though with larger constant $(\det L)^2\geq \det L$). One cannot hope for such a simple expression for non-full rank lattices because any containment $c\mathbb{Z}^n\subseteq L$ implies $L$ is full-rank, but in cryptography we typically work with full-rank lattices, so this doesn't really matter. $\endgroup$
    – Mark Schultz-Wu
    Jun 26, 2023 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.