6.2 q-ary lattices

A q-ary lattice is a lattice defined by linear equations modulo an integer $q$. The points themselves live in ordinary integer space. The modular condition decides which of those integer points belong to the lattice. This construction connects the algebra of Short Integer Solution (SIS) and Learning With Errors (LWE) to geometric problems such as finding short or nearby lattice vectors.

The modular-kernel lattice

Let $A\in\mathbb{Z}_q^{k\times m}$. Its modular-kernel lattice is the set of integer vectors whose product with $A$ is zero modulo $q$:

It is closed under addition and negation, so it is a lattice. Every vector in $q\mathbb{Z}^m$ belongs to it, which makes the lattice full rank even when$A$ has only a few rows. The superscript perpendicular describes the modular kernel; it is not the same as taking the Euclidean orthogonal complement over real numbers.

Worked example with q = 5

Choose $q=5$ and the one-row matrix $A=[1\;2]$. A point $(x,y)\in\mathbb{Z}^2$ is in the lattice when$x+2y\equiv0\pmod5$. Examples include $(0,0)$,$(-2,1)$, $(1,2)$, and $(5,0)$. The point$(1,1)$ is excluded because its modular sum is 3.

A basis is $b_1=(-2,1)$ and $b_2=(5,0)$. Any integer combination of these vectors satisfies the congruence. Conversely, if $x+2y=5t$, then $(x,y)=y(-2,1)+t(5,0)$. That proves the basis generates every solution, not merely some of them.

The determinant is 5 because the modular equation accepts one of every five residue classes in $\mathbb{Z}^2$. More generally, when $q$ is prime and $A$ has row rank $k$ modulo $q$, this kernel lattice has determinant $q^k$. If the rows are dependent, use the actual rank instead.

The related image lattice

A second q-ary lattice collects integer vectors whose residues lie in the row span of $A$:

For the example above, its points have residues among the multiples of $(1,2)$ modulo 5. These two lattices are related by $\Lambda_q(A)^*=(1/q)\Lambda_q^\perp(A)$. The equality is useful, but the two sets are not identical: the factor of $1/q$ matters. See the dual lattice guide for why taking a dual involves integer inner products.

What do SIS and LWE ask about these lattices?

SIS asks for a nonzero short vector satisfying $Ax=0\pmod q$. In other words, it asks for a short point in $\Lambda_q^\perp(A)$. The word “short” is essential: a vector such as $(q,0,\ldots,0)$ is always an easy modular-kernel solution, but a cryptographic SIS challenge sets a smaller norm bound.

In LWE, a public matrix and a noisy modular product define a point close to a structured lattice or coset. An attacker may use a closest-vector or embedding attack, while a dual attack searches for short modular relations that distinguish the noisy samples from uniform data. The exact lattice and attack dimensions depend on which samples are used; the tiny example here explains the geometry, not a real security parameter.

What to read next

Read SIS for the short-vector problem, LWE for noisy equations, and parameter selection for how attack costs are estimated. For the formal treatment, see Peikert’s A Decade of Lattice Cryptography and Micciancio’s duality lecture.