Short Integer Solution (SIS) — Lattice One-Way Functions

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.

Beginner's Intuition 💡

If LWE is about hiding a secret in noise, Short Integer Solution (SIS) is about solving a uniquely impossible puzzle.

Imagine having a massive dictionary where every single word is randomly assigned a 10-digit number. Your goal is to find two very short, almost identical words (like "car" and "cat") whose 10-digit numbers somehow magically combine to equal exactly zero.

It's easy to find some combination of thousands of words that equals zero, but finding a short combination (just a few simple words) is incredibly difficult. This mathematical "needle in a haystack" problem is used to build robust digital signatures.

The SIS Problem — Precise Definition

Definition 29 — Short Integer Solution (SIS)

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

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

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

$Ax \equiv 0 \pmod{q} \quad \text{and} \quad \|x\| \leq \beta$

The constraint $Ax \equiv 0 \pmod{q}$ requires that the integer combination of columns of $$A$$ with weights given by $$x$$ sums to zero modulo $$q$$ . The constraint $\|x\| \leq \beta$ requires the solution to be short — the entries of $$x$$ must be small integers, not arbitrary modular combinations.

Existence: When $m > n \log q$ , solutions with $\|x\|_\infty \leq 1$ exist by a pigeonhole argument (there are more columns than the image space can accommodate). The hard part isfinding such a solution for a given random $$A$$ .

Hardness regime: SIS is believed computationally hard when $\beta < q$ and $\beta \geq \sqrt{m} \cdot q^{n/m}$ (the Minkowski bound on the first minimum of the solution lattice). In this regime, short solutions exist but cannot be found efficiently without solving SVP.

SIS as SVP in a q-ary Lattice

SIS is naturally a lattice problem. The set of all solutions to $Ax = 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) = \{ x \in \mathbb{Z}^m : Ax \equiv 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 $\|x\| \leq \beta$ requires $\beta \geq \lambda_1$ . The SIS problem is hard when $\beta$ is much smaller than $$q$$ but larger than $\lambda_1$ .

SIS and One-Way Functions — The Ajtai 1996 Construction

SIS was the first lattice problem shown to support a one-way function with a worst-case hardness proof. Ajtai's 1996 paper is the founding result of modern lattice cryptography. Before Ajtai, all practical cryptographic hardness assumptions were average-case — you hoped that random instances were hard. Ajtai proved they must be.

Theorem 7 — Ajtai's Reduction and One-Way Function (1996)

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

The one-way function: For a random matrix $A \in \mathbb{Z}_q^{n \times m}$ , define:

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

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

This function is one-way: given $$f_A(x) = y$$ , computing any preimage is hard. Moreover, it is collision-resistant: finding two distinct $x \neq x^\prime$ with $f_A(x) = f_A(x^\prime)$ requires finding a short $z = x - x^\prime \in \{-1, 0, 1\}^m$ with $Az = 0 \pmod{q}$ — exactly a SIS solution with $\beta = \sqrt{m}$ .

What makes this historic: The security proof is a worst-case to average-case reduction. Solving SIS on a random $$A$$ is at least as hard as solving SVP on the worst possible lattice in dimension $$n$$ . There are no easy instances — a random $$A$$ is as hard as any $$A$$ .

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.

Ring-SIS — Defined over Polynomial Rings

Plain SIS requires an $n \times m$ matrix with $m \gg n$ — this is expensive in terms of key size and computation. Ring-SIS replaces integer matrices with polynomial ring elements, achieving the same hardness with dramatically smaller objects.

Definition — Ring-SIS

Let $R = \mathbb{Z}[x]/(x^n + 1)$ and $R_q = R/qR = \mathbb{Z}_q[x]/(x^n + 1)$ .

The Ring-SIS problem with parameters $(n, q, m, \beta)$ is: given $$m$$ uniformly random ring elements $a_1, \ldots, a_m \in R_q$ , find a nonzero vector $(z_1, \ldots, z_m) \in R^m$ with small coefficients satisfying:

$\sum_{i=1}^m a_i \cdot z_i \equiv 0 \pmod{q} \quad \text{and} \quad \|(z_1, \ldots, z_m)\| \leq \beta$

Each ring element in $$R_q$$ encodes $$n$$ integers. A single Ring-SIS instance with $$m$$ ring elements corresponds to a plain SIS instance with an $n \times mn$ integer matrix — but the ring structure means only $$m$$ elements need to be stored, not $$mn$$ .

Hardness: Ring-SIS reduces to worst-case SVP on ideal lattices — lattices that are ideals in $$R$$ . The hardness assumption is slightly stronger than for plain SIS (ideal lattices have more structure), but no attack exploiting this structure is known.

Module-SIS: Used in Dilithium (ML-DSA). Generalizes Ring-SIS to modules of rank $$k$$ : find a short vector in $R^{k+\ell}$ mapping to zero under a random $(k \times \ell)$ module matrix over $$R_q$$ . This is the direct analogue of Module-LWE for signatures. Hardness reduces to worst-case SVP on module lattices.

Used in FALCON: Falcon's signature security reduces to Ring-SIS over $\mathbb{Z}[x]/(x^n + 1)$ with $$n = 512$$ or $$1024$$ . Forging a Falcon signature requires finding a short vector in the NTRU lattice coset defined by the message hash — a Ring-SIS instance.

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^\prime$ with $Ax = Ax^\prime \pmod{q}$ , i.e., $A(x - x^\prime) = 0 \pmod{q}$ . Since $x - x^\prime \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^\prime$ 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 ↗