up:: The New Standards MOC

Short Integer Solution (SIS)

The Short Integer Solution problem is one of the two core lattice problems that post-quantum cryptography is built on, and it is the one that governs signatures. Where Learning With Errors hides a secret inside noise and asks you to recover it, SIS hands you a random modular linear system and asks for a short nonzero vector that the system sends to zero. Any vector at all satisfies the equation if you allow it to be large, so the entire difficulty lives in the word “short.” Finding a small solution among the huge number of large ones is believed intractable at cryptographic sizes on any computer, and that difficulty is exactly what stops an attacker from forging a lattice signature. Its module variant, Module-SIS, is the unforgeability foundation of ML-DSA, the primary post-quantum signature standard.

Source: Miklós Ajtai, “Generating hard instances of lattice problems,” STOC 1996, per Wikipedia, “Short integer solution problem”.

The short version:

• SIS asks for a short answer, not a hidden secret. Given a random matrix over a modular ring, find a short nonzero vector z with Az ≡ 0. Large solutions are trivial to find, so the whole security is the shortness constraint.
• It is the signature-side partner of LWE. LWE governs confidentiality (recover a secret from noise), SIS governs authenticity (find a short solution), and ML-DSA rests on both together.
• Ajtai introduced it in 1996 and proved the founding worst-case-to-average-case reduction of lattice cryptography, showing a random SIS instance is hard if worst-case lattice problems like the shortest-vector problem are hard.
• The module variant is what ships. Module-SIS structures the problem over polynomial modules for efficiency, and it is the assumption behind ML-DSA’s resistance to forgery.
• It resists quantum attack because it is a lattice problem with no periodic structure for Shor’s algorithm to exploit, and the best known attacks are lattice-reduction algorithms that run in exponential time.

Picture a machine that takes any list of whole numbers you feed it and, after some fixed scrambling, spits out a single verdict of zero or not-zero. Feeding it enormous numbers to force a zero is easy, because there is endless room to make the scrambling cancel out when the inputs are allowed to be huge. The challenge is different. I ask you to make the machine say zero using only small numbers, none of them larger than a tight bound I set. On a tiny machine you could search by hand. On a machine with hundreds of inputs and a scrambling drawn at random, the small combinations that happen to cancel are needles buried in an astronomically large haystack of large ones, and no known method finds them in a practical amount of time. That search for a small, exactly-cancelling input is the Short Integer Solution problem.

What is the Short Integer Solution problem?

The Short Integer Solution problem asks you to find a short nonzero integer vector in the null space of a random modular matrix. Formally, given a uniformly random matrix A with entries modulo a prime q, the task is to find a nonzero integer vector z such that Az ≡ 0 (mod q) and the size of z, measured by a norm, stays below a fixed bound. Without the size bound the problem is trivial, because a modular linear system has many solutions and ordinary linear algebra produces one immediately. The bound is the entire trick. If the bound is loose, short solutions are plentiful and easy to find; if it is tight, short solutions become rare and locating one is the hard problem.

Source: Miklós Ajtai, “Generating hard instances of lattice problems,” STOC 1996, per Wikipedia, “Short integer solution problem”.

This is a lattice problem at its core. The set of all integer vectors that A sends to zero forms a high-dimensional grid, a lattice, and asking for a short nonzero member of that grid is asking for a short vector in the lattice. SIS is therefore an averaged, cryptography-friendly cousin of the raw geometric question of finding the shortest nonzero point in a lattice. That connection is exact. It is the content of Ajtai’s founding theorem.

What did Ajtai prove, and why did it matter?

Ajtai’s 1996 result launched lattice-based cryptography by proving the first worst-case-to-average-case reduction in the field. He showed that solving a randomly chosen SIS instance is at least as hard as solving certain lattice problems, including the shortest-vector problem, in their absolute worst case. That was a landmark because it let cryptographers build one-way functions whose average-case security, the security of a typical random key, was provably tied to the worst-case hardness of a famous, long-studied geometric problem. Most hard problems used in cryptography offer no such guarantee, so a random instance could in principle be far easier than the hardest one; SIS closed that gap for the signature side of the lattice world.

Source: Miklós Ajtai, “Generating hard instances of lattice problems,” STOC 1996, per Wikipedia, “Short integer solution problem”.

The parallel with LWE is exact and worth holding onto. Regev’s later worst-case-to-average-case reduction gave the same kind of guarantee to the confidentiality side, and Ajtai’s earlier reduction is the one that anchors the authenticity side. The two together are why lattices have a stronger theoretical footing than RSA or elliptic-curve cryptography ever had, where security rests on average-case assumptions with no proven link to any worst-case problem.

How does SIS underpin lattice signatures?

SIS underpins signatures because forging one is equivalent to solving it. A lattice signature scheme is arranged so that a valid signature is, in effect, a short vector satisfying a linear relation tied to both the signer’s public key and the message being signed. The legitimate signer produces that short vector using a private shortcut. An attacker without the private key who wants to forge a signature on a message of their choosing has to produce a short vector satisfying the same relation from scratch, and that is exactly an instance of SIS. Verification checks two things: that the relation holds, and that the vector is genuinely short. The shortness check is what makes forgery hard, because dropping it would let any large vector pass.

Source: NIST, “Module-Lattice-Based Digital Signature Standard,” FIPS 204, August 13, 2024 (ML-DSA built on Module-LWE and Module-SIS); mechanism per Module-SIS reference.

The construction that connects SIS to a real signature is Fiat-Shamir with aborts, and the “aborts” part is rejection sampling, which forces the short vectors the signer publishes to reveal nothing about the private key. So a lattice signature deployment leans on SIS for its unforgeability, on Module-LWE for the secrecy of its signing key, and on rejection sampling to keep the two from leaking through the signatures themselves. All three are needed, and Module-SIS is the specific one that answers “why can’t an attacker forge this?”

What is the module variant, and where is it used?

The module variant, Module-SIS, is the form the standards actually deploy, and it exists for the same efficiency reason the module variant of LWE exists. Plain SIS works with large unstructured matrices of integers, which is conservative but heavy. Module-SIS lifts the problem into a module of polynomials, meaning the matrix entries and the solution vector are elements of a polynomial ring rather than plain integers, so the same security fits in far fewer bytes and computes far faster. The module dimension is a dial the designer turns to reach different security levels over the same underlying ring.

Source: NIST, FIPS 204, August 13, 2024; parameter details per Module-SIS reference (ring Z_q[x]/(x^256 + 1) with q = 8380417, a 23-bit prime, and module dimensions rising across ML-DSA-44, ML-DSA-65, and ML-DSA-87).

Signature parameter set	NIST security level	Governing problems
ML-DSA-44	Level 2 (SHA-256 collision strength)	Module-SIS + Module-LWE
ML-DSA-65	Level 3 (~AES-192)	Module-SIS + Module-LWE
ML-DSA-87	Level 5 (~AES-256)	Module-SIS + Module-LWE

Module-SIS never appears by name in a protocol or a cryptographic inventory. What appears is ML-DSA with a parameter set, and Module-SIS is the hardness assumption underneath it. Anywhere ML-DSA signs, whether a TLS certificate, a code-signing operation, a document signature, or an identity token, Module-SIS is the problem an attacker would have to solve to forge that signature.

Why does SIS resist quantum attack?

SIS resists quantum attack for the same reason the rest of the lattice family does: it is a geometric problem with no periodic number-theoretic structure, and periodic structure is the one thing Shor’s algorithm needs. Shor’s breaks RSA and elliptic-curve cryptography by converting factoring and the discrete logarithm into period-finding, which a quantum computer solves efficiently. Finding a short vector in the null space of a random modular matrix has no period to find, so Shor’s algorithm has nothing to hook into and does not apply.

Source: NIST, FIPS 204, August 13, 2024; Shor’s scope per P. W. Shor, SIAM J. Comput. 1997, SIAM.

The best known attacks on SIS are lattice-reduction algorithms, the BKZ family, which run in exponential time classically. The best quantum algorithms give only a modest speedup over that, not the quadratic discount of Grover’s and certainly not the polynomial-time break of Shor’s, and ML-DSA’s parameter sets are chosen with that modest quantum discount already priced in. As with LWE, the more serious open question for SIS was never quantum. It is whether classical lattice reduction improves faster than expected, which is watched continuously and is why the standardized parameters carry deliberate margin and why hash-based SLH-DSA exists as a non-lattice signature backup.

Common misconceptions

• “SIS and LWE are the same problem.” They are cousins in the same lattice family but distinct. LWE is about recovering a secret hidden in noise, which governs confidentiality, while SIS is about finding a short solution to a linear system, which governs signature unforgeability. ML-DSA needs both.
• “Finding a solution to Az ≡ 0 is easy, so SIS is easy.” Finding some solution is easy, because large solutions are everywhere. Finding a short one below the bound is the hard part, and dropping the shortness constraint is exactly what would make a signature forgeable.
• “SIS is a new, untested assumption.” It dates to Ajtai’s 1996 work, which founded lattice cryptography with the first worst-case-to-average-case reduction. It is younger than RSA but comes with a theoretical guarantee RSA never had.
• “A quantum computer will break SIS the way it breaks RSA.” There is no known quantum algorithm that breaks SIS. Shor’s needs periodic structure that lattice problems lack, and the best quantum attacks on SIS give only a modest speedup that the parameters account for.
• “Signatures are exposed to harvest-now-decrypt-later, so SIS is urgent like a key exchange.” Signatures provide authenticity, not confidentiality, so they carry no harvest-now-decrypt-later exposure. A signature is only at risk once a live quantum computer exists, which is why the signature migration runs on a slower track than the key-exchange one.

Questions people ask

What is the Short Integer Solution problem in simple terms? It is the task of finding a small, nonzero list of whole numbers that a random modular linear system sends exactly to zero. Large solutions are easy to find, so the whole difficulty is the requirement that the solution be short, and that difficulty is what makes lattice signatures impossible to forge.

Who introduced SIS and when? Miklós Ajtai introduced it in 1996, in work presented at STOC titled “Generating hard instances of lattice problems.” The same paper proved the founding worst-case-to-average-case reduction of lattice cryptography, connecting a random SIS instance to the worst-case hardness of lattice problems like the shortest-vector problem.

How is SIS different from LWE? LWE asks you to recover a secret hidden in noisy equations, which is the confidentiality side. SIS asks you to find a short solution to a linear system, which is the authenticity side. LWE governs why an encryption key stays secret, and SIS governs why a signature cannot be forged. ML-DSA rests on both.

What is Module-SIS? Module-SIS is the efficient variant of SIS used in the standards, structured over a module of polynomials rather than plain integers, which shrinks keys and speeds up the math while letting the designer tune security by changing the module dimension. It is the unforgeability foundation of ML-DSA.

Does a quantum computer break SIS? No. SIS is a lattice problem with no periodic structure for Shor’s algorithm to exploit. The best known attacks are lattice-reduction algorithms that run in exponential time, quantum computers give only a modest speedup over them, and ML-DSA’s parameters are set with that discount priced in.

Do I need to understand SIS to migrate to ML-DSA? No. The migration work is inventory, sizing, and testing, and Module-SIS lives inside the libraries and hardware you integrate. Understanding it tells you why ML-DSA signatures cannot be forged and why hash-based SLH-DSA exists as a diversity hedge, which is a leadership question rather than an implementation one.

---

Everything here is the map, given freely. When your team needs its signature estate inventoried and sequenced onto the post-quantum standards, that’s what an alignment briefing is for.

Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.