Short Integer Solution (SIS)

A Problem Chosen at Random

The previous page ended with a promise: to turn a worst-case lattice problem into the random-looking, average-case problem that an encryption scheme can sample from, and to show that breaking such a scheme would solve the worst-case problem underneath. This page delivers the first half of that promise. It defines the problem on which the earliest lattice-based cryptography was built, and it establishes the guarantee that makes the problem trustworthy.

The distinction that organizes everything here is between worst-case and average-case hardness. Cryptography needs problems that are hard on a randomly chosen instance, because a scheme generates its keys by sampling — an adversary faces whatever instance the sampling produced, not one an adversary got to choose. Nearly every classical construction rests on an average-case assumption of exactly this kind. A scheme built on the difficulty of factoring assumes not that factoring is hard in the worst case, but that it is hard for integers drawn from some specified distribution. This raises a question with no clean answer: which distribution? Some integers factor easily, and one must arrange the sampling to avoid them, without any guarantee that the avoided cases are the only easy ones.

Lattice cryptography escapes this question. The problem defined below is hard on average — over its own natural distribution — because a worst-case lattice problem is hard at all, with no distribution left to second-guess. That is the guarantee the final section makes precise; the intervening sections build the object it applies to.

The Problem

Fix a dimension \(n\) and a modulus \(q\), and work in the finite additive group \(\mathbb{Z}_q^n\) of integer vectors modulo \(q\). The problem takes as input a collection of uniformly random elements of this group and asks for a short integer combination of them that vanishes.

Here \(n\) is the main hardness parameter; one should picture it as large, with \(q\) a small polynomial in \(n\). The number of samples \(m\) is of secondary importance and is often left unspecified, for a reason the next section makes structural. Two constraints on the parameters are forced by the shape of the problem.

First, the norm bound cannot be dropped. Without the requirement \(\|\mathbf{z}\| \leq \beta\), a solution is trivial to produce by standard linear algebra over \(\mathbb{Z}_q\): the equation \(\mathbf{A}\mathbf{z} = \mathbf{0}\) is a homogeneous linear system, and once \(m\) exceeds \(n\) it has nonzero solutions that are found in polynomial time. The difficulty is created entirely by demanding that the solution be short. For the same reason one must take \(\beta \lt q\): otherwise the vector \(\mathbf{z} = (q, 0, \dots, 0)\) is always a legitimate solution, since \(q \, \mathbf{a}_1 \equiv \mathbf{0} \pmod q\), and it is nonzero and trivial to write down.

Second, the bound and the sample count must be large enough that a solution is guaranteed to exist — otherwise the problem may be asking for something that is not there. This is where a counting argument enters, and it is worth stating precisely, because the same argument reappears in the next two sections in two different roles.

Finding the solution is a separate matter from knowing it exists, and the difficulty of finding it — on a random instance — is what the following sections pin down, first geometrically, then cryptographically, and finally as a worst-case guarantee.

The Lattice Behind the Problem

The problem was posed algebraically — a matrix, a linear equation modulo \(q\), a norm bound — but its difficulty is geometric, and naming the geometry is what connects it to everything the previous pages built. The set of all integer vectors that the matrix sends to zero is not an arbitrary collection. It is a lattice.

That this set is a lattice — a discrete additive subgroup of \(\mathbb{R}^m\) — can be seen directly. It is a subgroup of \(\mathbb{Z}^m\): the map \(\mathbf{z} \mapsto \mathbf{A}\mathbf{z} \bmod q\) is a homomorphism from \(\mathbb{Z}^m\) to the finite group \(\mathbb{Z}_q^n\), and \(\mathcal{L}^\perp(\mathbf{A})\) is its kernel. A kernel is a subgroup, and a subgroup of \(\mathbb{Z}^m\) is discrete because \(\mathbb{Z}^m\) is. It is full-rank because it contains \(q\mathbb{Z}^m\), which already spans \(\mathbb{R}^m\); the lattice fills the whole space rather than collapsing into a proper subspace. Every tool the geometry pages developed for lattices in general applies to it without modification.

SIS as an Average-Case Shortest-Vector Problem

With the lattice named, the problem reads differently. A solution to \(\mathrm{SIS}_{n, q, \beta, m}\) is a nonzero \(\mathbf{z} \in \mathcal{L}^\perp(\mathbf{A})\) with \(\|\mathbf{z}\| \leq \beta\) — a short nonzero vector of the \(q\)-ary lattice. This is precisely a shortest-vector problem on \(\mathcal{L}^\perp(\mathbf{A})\), with the norm bound \(\beta\) playing the role of the target length. The one structural difference from the worst-case problems of the previous page is decisive: the lattice here is not adversarial but random, drawn from the distribution induced by a uniformly random \(\mathbf{A}\). SIS is the average-case shortest-vector problem on this family of \(q\)-ary lattices.

The matrix \(\mathbf{A}\) acts as a parity check in the language of coding theory: it does not generate the lattice but tests membership in it, exactly as a parity-check matrix tests membership in a linear code. This viewpoint also explains why the sample count \(m\) was called secondary. Two monotonicities follow from the definition and pin down how the parameters govern difficulty.

One variant is worth naming, because the cryptographic constructions built on SIS use it freely. Instead of asking for a short vector in the kernel, one may fix a target \(\mathbf{u} \in \mathbb{Z}_q^n\) and ask for a short integer solution to \(\mathbf{A}\mathbf{x} = \mathbf{u}\). The set of all solutions, ignoring the norm bound, is a coset \(\mathbf{c} + \mathcal{L}^\perp(\mathbf{A})\) of the \(q\)-ary lattice, for any particular solution \(\mathbf{c}\). Finding a short element of a lattice coset is the inhomogeneous form of the problem; for the parameters that concern cryptography it is essentially equivalent to the homogeneous one, and we will not distinguish them further.

One-Wayness and Collisions

The counting argument of the first section did more than guarantee that a solution exists. It exhibited that solution as the difference of two inputs that collide — two distinct \(\mathbf{x}, \mathbf{x}'\) with \(\mathbf{A}\mathbf{x} = \mathbf{A}\mathbf{x}'\). Read in that light, hardness of SIS is exactly the statement that such collisions are hard to find, and this is what turns the problem into a cryptographic primitive rather than a mere curiosity.

Restrict the matrix to act on short inputs. Fix \(m\) somewhat larger than \(n \log_2 q\) and consider the function that reads a bit-string and returns its image modulo \(q\), \[ f_{\mathbf{A}} : \{0, 1\}^m \to \mathbb{Z}_q^n, \qquad f_{\mathbf{A}}(\mathbf{x}) = \mathbf{A}\mathbf{x} \bmod q. \] The domain has \(2^m\) elements and the codomain \(q^n\); when \(m \gt n \log_2 q\) the domain is strictly larger, so \(f_{\mathbf{A}}\) is a compressing function and collisions are guaranteed to exist. The content of SIS is that they cannot be found efficiently.

Collision Resistance

A collision for \(f_{\mathbf{A}}\) is a pair \(\mathbf{x} \neq \mathbf{x}'\) in \(\{0, 1\}^m\) with \(f_{\mathbf{A}}(\mathbf{x}) = f_{\mathbf{A}}(\mathbf{x}')\). Any collision immediately yields an SIS solution: the difference \(\mathbf{z} = \mathbf{x} - \mathbf{x}' \in \{-1, 0, 1\}^m\) is nonzero, has \(\mathbf{A}\mathbf{z} = \mathbf{0}\), and satisfies \(\|\mathbf{z}\| \leq \sqrt{m}\). Conversely an algorithm that finds short SIS solutions can be turned into one that finds collisions. So the family of functions \(\{f_{\mathbf{A}}\}\), indexed by the random choice of \(\mathbf{A}\), is collision resistant exactly when \(\mathrm{SIS}_{n, q, \sqrt{m}, m}\) is hard: no efficient algorithm, given a random \(\mathbf{A}\), finds a collision with non-negligible probability. The bit-domain \(\{0, 1\}^m\) is not essential; any sufficiently large set of short integer vectors serves the same purpose.

A weaker guarantee is worth separating out, because it names a distinct primitive. The function family is one-way if, given \(\mathbf{A}\) and the image \(f_{\mathbf{A}}(\mathbf{x})\) of a random input \(\mathbf{x}\), no efficient algorithm recovers any preimage with non-negligible probability. Collision resistance is the stronger property: finding two inputs with the same image is at least as hard as inverting the function, since a preimage-finder can be used to manufacture collisions. Every collision-resistant family is therefore one-way, and SIS delivers the stronger of the two. Both are foundational objects of cryptography — the ingredients from which hash functions, identification schemes, and digital signatures are built.

The Worst-Case Guarantee

Everything so far has treated SIS as a random problem and asserted, without justification, that it is hard on average. That assertion is now made precise, and its justification is the property that sets lattice cryptography apart from every construction built on factoring or the discrete logarithm: the average-case problem is hard because a worst-case problem is. Solving random SIS instances, even with small probability, would solve every instance of a lattice problem from the previous page.

The values of \(m\) and \(q\) beyond the lower bound play no role in the guarantee; what governs the strength of the conclusion is the norm bound \(\beta\), through the approximation factor \(\gamma = \beta \cdot \mathrm{poly}(n)\) it produces. A smaller \(\beta\) — a stricter demand on the SIS solution — yields a smaller \(\gamma\), a harder worst-case problem, and thus a stronger security guarantee. The theorem is proved by exhibiting a reduction: an algorithm that, given a basis of an arbitrary lattice \(\mathcal{L}\) and access to an oracle solving random SIS, produces short independent vectors in \(\mathcal{L}\). The whole difficulty is that the oracle answers only for uniformly random instances, while \(\mathcal{L}\) is arbitrary; the reduction must manufacture a random-looking SIS instance whose solution reaches back into the fixed lattice.

The Core Step

The reduction maintains a set \(\mathbf{S} \subset \mathcal{L}\) of linearly independent lattice vectors, beginning with the input basis, and repeatedly replaces it by a shorter set \(\mathbf{S}'\) with \(\|\mathbf{S}'\| \leq \|\mathbf{S}\|/2\), where \(\|\mathbf{X}\|\) denotes the longest vector in the set. Iterating drives the set down until it can shrink no further, at which point its length certifies a solution to \(\mathrm{SIVP}_\gamma\); the same short independent set also settles \(\mathrm{GapSVP}_\gamma\), since its shortest member bounds \(\lambda_1\) from above while the promise gap bounds it from below. One iteration runs the following core step.

Two claims complete the argument, and both turn on the vectors \(\mathbf{v}_i\) being genuinely well spread. First, the instance \(\mathbf{A}\) handed to the oracle must look uniformly random, since that is the only distribution on which the oracle is assumed to work. It can be shown, through the lattice smoothing technique, that when \(\mathbf{S}\) is still longer than a \(\mathrm{SIVP}_\gamma\) solution — precisely the regime where the reduction has not yet finished — the vectors \(\mathbf{v}_i \bmod q\mathcal{L}\) are nearly uniform over \(\mathcal{L}/q\mathcal{L}\), and multiplication by \(\mathbf{B}^{-1}\) carries this to a nearly uniform \(\mathbf{a}_i\) over \(\mathbb{Z}_q^n\). Second, the output vectors must not all collapse to zero or into a proper subspace, even against an adversarial oracle; the same spread guarantees that \(\mathbf{v} = \mathbf{V}\mathbf{z}/q\) retains enough randomness that a full-rank set is obtained after enough steps. The reduction is thereby valid, and the theorem follows.

A concrete choice of parameters makes the guarantee tangible. Taking \(q = 2^{2n}\) and \(m = 4n^2\), an oracle that finds a nonzero \(\{-1, 0, 1\}\)-combination summing to zero modulo \(q\), for random \(\mathbf{a}_1, \dots, \mathbf{a}_m \in \mathbb{Z}_q^n\), yields a polynomial-time algorithm for \(\mathrm{SIVP}\) with a polynomial approximation factor on any lattice. The modulus is large and the factor is far from optimal at this setting; a long line of refinements has since driven the modulus down to nearly \(\beta\) and the factor into the range where the problem is believed genuinely hard, but the mechanism is already the one shown above.