Lattices.io — Mathematical Lattices & Post-Quantum Cryptography

LWE and SIS are mathematical duals of each other. Where LWE asks you to recover a hidden secret from noisy linear equations, SIS (Short Integer Solution) asks you to find a short nonzero integer vector in the kernel of a random matrix — a vector $$z$$ such that $Az = 0 \ (\text{mod} \ q)$ and $\|z\|$ is small. This problem underlies lattice-based hash functions and digital signatures.

The conceptual difference: LWE is about finding hidden information (secret $$s$$ ) given noisy observations. SIS is about finding a short collision in a linear map — two short vectors that map to the same value. This makes SIS the natural foundation for collision-resistant hash functions and digital signatures.

The Problem Statement

Definition 29 — Short Integer Solution (SIS)

Parameters: Dimension $$n$$ , modulus $$q$$ , number of columns $$m$$ , bound $\beta$ .

Input: A uniformly random matrix $A \in \mathbb{Z}_q^{n \times m}$ .

Goal: Find a nonzero integer vector $z \in \mathbb{Z}^m$ such that:

$Az = 0 \pmod{q} \quad \text{and} \quad \|z\| \leq \beta$

Such a vector $$z$$ exists when $m > n \log q$ (by pigeonhole), so the problem is never vacuous. The challenge is finding one with the small norm constraint $\|z\| \leq \beta$ .

The Lattice Perspective

SIS is naturally a lattice problem. The set of all solutions to $Az = 0 \pmod{q}$ forms a lattice — the q-ary lattice $\Lambda_q^\perp(A)$ . Finding a short SIS solution means finding a short vector in this lattice. This is an instance of SVP.

SIS as SVP in a q-ary Lattice

The solution lattice is:

$\Lambda_q^\perp(A) = \{ z \in \mathbb{Z}^m : Az = 0 \pmod{q} \}$

This lattice has determinant $$q^n$$ (it contains $q\mathbb{Z}^m$ as a sublattice). Minkowski's bound gives:

$\lambda_1(\Lambda_q^\perp(A)) \leq \sqrt{m} \cdot q^{n/m}$

A short SIS solution with $\|z\| \leq \beta$ requires $\beta \geq \lambda_1$ . The SIS problem is hard when $\beta$ is much smaller than $$q$$ but larger than $\lambda_1$ .

Worst-Case Hardness: Ajtai's Theorem

SIS is special because it was the first problem to admit a worst-case to average-case reduction in cryptography — Ajtai's 1996 breakthrough that launched modern lattice cryptography.

Theorem 7 — Ajtai's Reduction (1996)

If there exists a polynomial-time algorithm that solves SIS with parameters $(n, m, q, \beta)$ for a uniformly random $$A$$ , then there exists a quantum polynomial-time algorithm solving SVP on arbitrary lattices in dimension $$n$$ with approximation factor $\tilde{O}(n \cdot \beta / q)$ .

The direction of the reduction: worst-case lattice problems are no harder than average-case SIS. Equivalently: average-case SIS is at least as hard as worst-case lattice problems. So breaking a random SIS instance is at least as hard as solving SVP on the hardest possible lattice in that dimension.

This is a qualitatively stronger security guarantee than is typical in cryptography. Most cryptographic systems are based on the heuristic belief that a specific average-case problem is hard. Ajtai's theorem says: SIS is hard on average if SVP is hard in the worst case. The worst-case/average-case equivalence eliminates any possibility of finding "easy" random instances.

Collision-Resistant Hash Functions from SIS

SIS directly gives collision-resistant hash functions. Define the hash function:

Construction 8 — SIS Hash Function

Fix a public random matrix $A \in \mathbb{Z}_q^{n \times m}$ . Define the hash function:

$h_A : \{0,1\}^m \to \mathbb{Z}_q^n$

$h_A(x) = Ax \pmod{q}$

A collision is two distinct bit strings $x \neq x'$ with $Ax = Ax' \pmod{q}$ , i.e., $A(x - x') = 0 \pmod{q}$ . Since $x - x' \in \{-1, 0, 1\}^m$ , the difference vector is short — so finding a collision is exactly solving SIS with $\beta = \sqrt{m}$ .

By Ajtai's theorem: if SIS is hard, this hash function is collision-resistant — provably secure against any polynomial-time adversary.

SIS and Digital Signatures

SIS is also the foundation for lattice-based digital signatures. The key insight: a valid signature for a message is a short vector related to a random challenge. Forging a signature (producing a short vector without knowing the secret key) is an instance of SIS.

The signing equation

In Dilithium and related schemes, a signature $$z$$ for message $\mu$ satisfies:

$Az = t \cdot c + \text{small noise}$

where $$c$$ is a challenge derived from the message and $$t = As$$ is the public key. $$z$$ must be short (SIS solution) and consistent with the public key.

Forging = solving SIS

Forging a signature for a new message means finding a short $$z'$$ satisfying the verification equation without knowing $$s$$ . This is exactly an instance of SIS in the lattice defined by $$A$$ and the public key. Hardness of SIS implies unforgeability of the signature scheme.

Module-SIS

Dilithium and ML-DSA use Module-SIS: SIS over a polynomial ring module. This is Ring-SIS (SIS in a polynomial ring) lifted to a module of rank $$k$$ . Hardness of Module-SIS reduces to worst-case SVP on module lattices — the same hardness hierarchy as Module-LWE.

The Dual Relationship: SIS and LWE

SIS and LWE are not just both hard — they are formally dual to each other. The lattice $\Lambda_q^\perp(A)$ (the SIS lattice) and the lattice $\Lambda_q(A)$ (the LWE lattice) satisfy:

Theorem 8 — SIS/LWE Duality

$(\Lambda_q(A))^\vee = \frac{1}{q} \Lambda_q^\perp(A)$

The LWE lattice (finding the secret $$s$$ ) and the SIS lattice (finding a short kernel vector) are duals of each other up to scaling by $$q$$ .

This geometric duality explains why LWE and SIS have the same worst-case hardness reduction from SVP, and why the same BKZ attack (the "primal attack" on LWE and the "SIS attack") applies to both. The two hard problems are two views of the same lattice structure.

Parameter Regimes

SIS for hash functions

Typical: $$n = 256$$ , $q \approx 8380417$ (a prime), $$m = 512$$ , $\beta \leq 725$ . Hardness: solving this SIS requires BKZ with block size $\beta \approx 382$ , costing $\approx 2^{111}$ operations — above 128-bit security.

Module-SIS for ML-DSA-65

Module rank $$k = 4$$ , $\ell = 4$ , $$n = 256$$ , $$q = 8380417$$ , $\gamma_1 = 2^{19}$ , $\gamma_2 = (q-1)/32$ . Provides 192-bit security. Signature size: 3,293 bytes.

References and Further Reading

Key papers on SIS

Micciancio & Regev, "Lattice-based Cryptography" (2009) — §2 covers SIS and the Ajtai reduction in full detail. PDF ↗

Systematic Review of Lattice-Based Cryptography for Blockchain Applications (2025) — covers SIS-based constructions in distributed systems. iacis.org ↗