SIS Problem Statement: Short Integer Solution

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.

Intuition

If LWE is about hiding a secret in noise, Short Integer Solution (SIS) is about finding a small solution to a system that has many large ones.

You are given a random matrix modulo q and asked for a nonzero integer vector that the matrix sends to zero. Solutions are easy to find if they may be large. Finding one whose entries are all small is hard, and that difficulty is what lattice signatures and hash functions rely on.

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 is finding 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.

Rendering diagram…

The SIS problem at a glance. The modular equation places x in the kernel lattice; the norm bound asks for an unusually short nonzero point. That combination turns linear algebra into a hard lattice problem.

A row 1	11	3	1	12	15
A row 2	13	10	10	7	3
x	0	0	0	0	0

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 aclassical probabilistic polynomial-time algorithm solving approximate SVP (GapSVP / SIVP) on arbitrary lattices in dimension $n$ , with a polynomial approximation factor (in the modern form of Micciancio–Regev 2004 and Gentry–Peikert–Vaikuntanathan 2008, $\beta \cdot \tilde{O}(\sqrt{n})$ , for large enough $q$ ). Unlike Regev’s reduction for LWE, no quantum step is needed.

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))^* = \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 is estimated from the BKZ block size $b$ needed to reach a vector of norm $\leq \beta$ , at a Core-SVP cost of about $2^{0.292 b}$ operations. A 128-bit target therefore needs $b \gtrsim 440$ ; a block size around 380 would give only $\approx 2^{111}$ , below 128-bit security.

Module-SIS for ML-DSA-65

Module rank $k = 6$ , $\ell = 5$ , $n = 256$ , $q = 8380417$ , $\gamma_1 = 2^{19}$ , $\gamma_2 = (q-1)/32$ . Targets NIST security level 3 (comparable to AES-192). Signature size: 3,309 bytes.

Check Your Understanding

Q1. Solving Ax ≡ 0 (mod q) for some nonzero x is easy with linear algebra. What makes SIS hard?
Q2. The hash $h_A(x)$ = Ax mod q maps bit strings of length m to shorter outputs. Why does finding a collision mean solving SIS?
Q3. Why was Ajtai’s 1996 result such a big deal?
Q4. How do SIS and LWE relate?

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 ↗

← Previous2.3LWE & Ring-LWE Next →2.5Lattice SignaturesProving identity in a post-quantum world.

Unfamiliar symbol? The math reference explains the notation used across the site.

Found a mistake or something unclear? Report it on GitHub or email hello@ovasylenko.com.