Short Integer Solution (SIS) problem
The Short Integer Solution (SIS) problem asks for a short, nonzero integer vector that a given random matrix maps to zero modulo q. Introduced by Miklós Ajtai in 1996, it is the dual of Learning With Errors: where LWE hides a secret inside noise, SIS asks for a small combination of many public elements, and both reduce to worst-case lattice problems.
Why signatures use it
Finding a short solution is a collision-style task, which fits digital signatures: a valid signature is a short vector satisfying a verification equation that only the key holder can produce. Ajtai's 1996 result gave the first worst-case to average-case hardness reduction in cryptography (Ajtai, STOC 1996), later refined into the compact forms surveyed by Peikert (2015).
In deployed schemes
The module version, Module-SIS, secures ML-DSA (FIPS 204) alongside Module-LWE. SIS-style hardness also underlies hash-and-sign lattice constructions and any digital signature whose forgery would yield a short lattice vector.
Sources
- Generating Hard Instances of Lattice Problems (ACM (STOC 1996), 1996)
- A Decade of Lattice Cryptography (IACR ePrint Archive, 2015)
- FIPS 204, Module-Lattice-Based Digital Signature Standard (NIST, 2024)
Cite this entry
"Short Integer Solution (SIS) problem." postquantum.wiki. Updated July 11, 2026. https://postquantum.wiki/sis-problem@misc{pqwiki-sis-problem,
title = {Short Integer Solution (SIS) problem},
howpublished = {\url{https://postquantum.wiki/sis-problem}},
year = {2026},
note = {postquantum.wiki, updated 2026-07-11}
}