Shortest Integer Solution

The Shortest Integer Solution (SIS) problem is a lattice problem used as the hardness foundation for collision-resistant hash functions and lattice-based signature schemes. Unlike LWE, which is an indistinguishability problem, SIS is a search problem.

Assumption

Informally, SIS asks: given a random matrix $A \in Z_{q}^{n \times m}$ , find a nonzero short integer vector $z \in Z^{m}$ in the kernel of $A$ modulo $q$ . Such a vector always exists when $m > n lo g q$ (by a pigeonhole argument), so the hardness lies purely in finding one efficiently.

The assumption is parameterized by a lattice dimension $n$ , a column count $m$ , a modulus $q$ , and a norm bound $β$ . Typical parameters satisfy $q = poly (n)$ , $m = Θ (n lo g q)$ , and $β ≪ q$ .

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{sis}}_{n,m,q,\beta,\calA}(\secpar)$}
\begin{algorithmic}
\State $\mathbf{A} \getsr \ZZ_q^{n \times m}$
\State $\mathbf{z} \gets \calA(1^\secpar, \mathbf{A})$
\Return $[\mathbf{A}\mathbf{z} = \mathbf{0} \pmod{q} \;\wedge\; \mathbf{z} \neq \mathbf{0} \;\wedge\; \|\mathbf{z}\|_2 \leq \beta]$
\end{algorithmic}
\end{algorithm}

SIS is hard for $(n, m, q, β)$ with $m > n lo g q$ and $m \leq β < q$ , the regime in which a ${- 1, 0, 1}$ solution always exists and the trivial solution $q e_{1}$ is excluded, if for all efficient $A$ ,

Adv_{n, m, q, β, A}^{sis} (λ) := Pr [G_{n, m, q, β, A}^{sis} (λ) = 1]

is negligible. Here $∥ \cdot ∥$ is the Euclidean norm; the ISIS, Ring-SIS and Module-SIS variants below use the same norm on the coefficient vector. An $ℓ_{\infty}$ version ( $∥ z ∥_{\infty} \leq β$ ) is also used, e.g. Module-SIS in Dilithium — DKL+18.

Known Results

Worst-case hardness

Solving SIS on average (over a uniformly random $A$ ) is at least as hard as approximating the Shortest Vector Problem (GapSVP) and the Shortest Independent Vectors Problem (SIVP) to within polynomial factors in the worst case — Ajt96. This is a classical (non-quantum) worst-case-to-average-case reduction: any efficient algorithm that breaks SIS with noticeable probability on random inputs can be converted into an efficient algorithm for these worst-case lattice problems.

Collision-resistant hash functions

The function family ${f_{A} : z \mapsto Az mod q}$ , restricted to inputs $z \in {0, \dots, ⌊ β / m ⌋}^{m}$ , is a collision-resistant hash function family under SIS hardness — Ajt96, GGH96. Any collision $f_{A} (z) = f_{A} (z^{'})$ with $z \neq = z^{'}$ yields $A (z - z^{'}) = 0 (mod q)$ with $∥ z - z^{'} ∥ \leq β$ , which is exactly a SIS solution.

Total search complexity

For $m \geq n lo g q + 1$ and $m \leq β < q$ , SIS lies in PWPP (SIS ∈ PWPP): $z \mapsto Az mod q$ compresses ${0, 1}^{m}$ , and a collision gives a solution — standard. Constrained SIS, a generalization, is PPP-complete, and its weak form, a binary collision problem whose unconstrained case is the collision form of SIS, is PWPP-complete — SZZ18. Membership does not make SIS itself PWPP-hard.

Attacks

Lattice reduction (LLL/BKZ): The best known attacks find short vectors in the $q$ -ary lattice $Λ^{⊥} (A) = {z \in Z^{m} : Az = 0 (mod q)}$ using BKZ-style block reduction algorithms. Runtime is exponential in the block size $b$ : $2^{Θ (b)}$ with a sieving SVP oracle — standard.

Variations

ISIS (Inhomogeneous SIS)

Inhomogeneous SIS (ISIS) generalizes SIS by replacing the homogeneous target $0$ with an arbitrary syndrome. Given $A \leftarrow $ Z_{q}^{n \times m}$ and a target $t \leftarrow $ Z_{q}^{n}$ , find a short $z \in Z^{m}$ with $Az = t (mod q)$ and $∥ z ∥ \leq β$ .

ISIS is polynomially equivalent to SIS under mild parameter conditions, and is the hard-preimage problem underlying lattice-based digital signatures: a signature on a message $μ$ is a short preimage $z$ satisfying $Az = H (μ) (mod q)$ for a hash function $H$ — GPV08.

Ring-SIS

Ring-SIS replaces the random matrix $A \in Z_{q}^{n \times m}$ with a structured matrix defined by $ℓ = m / n$ elements of the polynomial ring $R_{q} = Z_{q} [x] / ⟨ x^{n} + 1 ⟩$ (for $n$ a power of 2). Specifically, the matrix is the concatenation of the negacyclic convolution matrices of random $a_{1}, \dots, a_{ℓ} \leftarrow $ R_{q}$ , and a Ring-SIS solution is a short nonzero $(z_{1}, \dots, z_{ℓ}) \in R^{ℓ}$ with $\sum_{i} a_{i} z_{i} = 0$ in $R_{q}$ — LM06, PR06.

Ring-SIS enjoys the same worst-case-to-average-case hardness as plain SIS, now reducing from ideal-SVP (shortest vectors in ideal lattices), and enables $O (n lo g n)$ -time ring products and $m lo g q$ -bit keys rather than $nm lo g q$ — LM06. A collision in the generalized compact knapsack $h (z_{1}, \dots, z_{ℓ}) = \sum_{i} a_{i} z_{i}$ on short inputs is a Ring-SIS solution, so Ring-SIS hardness gives collision-resistant hashing (Ring-SIS ⇒ CRHF) — LM06.

Module-SIS

Module-SIS interpolates between plain SIS (unstructured) and Ring-SIS (fully structured) by using rank- $k$ modules over $R_{q}$ . The random matrix $A \in R_{q}^{k \times ℓ}$ has ring elements as entries, and a Module-SIS solution is a short nonzero vector $z \in R^{ℓ}$ with $Az = 0$ in $R_{q}^{k}$ . Setting $k = 1$ recovers Ring-SIS; setting the ring degree $n = 1$ (so $R = Z$ ) recovers plain SIS — LS15.

Hardness of Module-SIS reduces to worst-case problems on module lattices — LS15. Dilithium (ML-DSA, FIPS 204) is unforgeable in the random-oracle model under Module-SIS together with Module LWE (Module LWE + Module-SIS ⇒ DS) — DKL+18.

Participates in

Builds on Shortest Integer Solution

ISIS (Inhomogeneous SIS) ⇔ SIS (via ISIS (Inhomogeneous SIS))
Module LWE + Module-SIS ⇒ DS (via Module-SIS)
Module-SIS ⇒ CRHF (via Module-SIS)
Ring-SIS ⇒ CRHF (via Ring-SIS)
SIS ⇒ DS
SIS ⇒ CRHF
SIS ∈ PWPP

Produces Shortest Integer Solution

Cryptology City

Explorer