Finite index quotient group, lattice crypto

user1035648

6/25/24, 8:12 PM

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)?

1 + 0

lattice-crypto

Score:1

Crypto

Mark

6/25/24, 8:49 PM

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.

+ 2

user1035648

6/26/24, 10:46 PM

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?

Mark

6/26/24, 10:54 PM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Finite index quotient group, lattice crypto

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.