Short Integer Solution

Short Integer Solution (SIS) is an average-case problem, which was introduced in 1996 by Miklós Ajtai. He introduced a family of one-way functions based on SIS and showed that SIS is hard to solve on average if a version of the shortest vector problem is hard in a worst-case scenario.

Formal Definition

SIS_n,m,q,β STANDARD

Let matrix $\mathbf{𝐀}\in {\mathbb{\mathbb{Z}}}_q^{n\times m}$ be chosen uniformly at random. An adversary is asked to find a short non-zero vector $\mathbf{𝐬}\in {\mathbb{\mathbb{Z}}}^m$satisfying $\mathbf{𝐀}\cdot \mathbf{𝐬}=\mathbf{𝟎}modq\wedge 0<\Vert \mathbf{𝐬}\Vert \le \beta$.

A solution to SIS without the condition $\Vert \mathbf{𝐬}\Vert \le \beta$ can be found using Gaussian elimination. Thus, the condition $\beta <q$ is required as otherwise $(q,0,\dots ,0)\in {\mathbb{\mathbb{Z}}}^m$ is a trivial solution.

Versions of SIS

ISIS_n,m,q,β - Inhomogeneous SIS EQUIVALENT

Let matrix $\mathbf{𝐀}\in {\mathbb{\mathbb{Z}}}_q^{n\times m}$and target vector $\mathbf{𝐭}\in {\mathbb{\mathbb{Z}}}_q^n$ be chosen uniformly at random. An adversary is asked to find a short vector $\mathbf{𝐬}\in {\mathbb{\mathbb{Z}}}^m$satisfying $\mathbf{𝐀}\cdot \mathbf{𝐬}=\mathbf{𝐭}modq\wedge \Vert \mathbf{𝐬}\Vert \le \beta$.

The inhomogeneous version of SIS introduces a target vector $\mathbf{𝐭}\in {\mathbb{\mathbb{Z}}}_q^n$, which is chosen uniformly at random. The probability of ending up in the homogeneous case with $\mathbf{𝐭}=\mathbf{𝟎}$ happens with probability $q^{-n}$, which allows removing the condition of $\mathbf{𝐬}$ being non-zero.

ISIS is as hard as SIS. A SIS instance can be reduced to ISIS using the last column of $\mathbf{𝐀}$ as target vector for ISIS. Any solution $\mathbf{𝐬}\in {\mathbb{\mathbb{Z}}}^{m-1}$ to the ISIS instance with challenge matrix ${\mathbf{𝐀}}_{[1:m-1]}$ and target vector ${\mathbf{𝐚}}_m$ yields a valid SIS solution $({\mathbf{𝐬}}^T,-1)\in {\mathbb{\mathbb{Z}}}^m$ of slightly larger norm. The reduction from ISIS to SIS requires index guessing a non-zero entry in the SIS solution and embedding the target vector at this position in the challenge matrix $\mathbf{𝐀}$.

NFSIS_n,m,q,β - Normal Form SIS EQUIVALENT

Let matrix $\overline{\mathbf{𝐀}}\in {\mathbb{\mathbb{Z}}}_q^{n\times m-n}$ be chosen uniformly at random and define $\mathbf{𝐀}=\left[\begin{array}{cc}{\mathbf{𝐈}}_n& \overline{\mathbf{𝐀}}\end{array}\right]$. An adversary is asked to find a short non-zero vector $\mathbf{𝐬}\in {\mathbb{\mathbb{Z}}}^m$satisfying $\mathbf{𝐀}\cdot \mathbf{𝐬}=\mathbf{𝐭}modq\wedge 0<\Vert \mathbf{𝐬}\Vert \le \beta$.

Normal Form SIS is related to the Hermite normal form of a uniformly random matrix $\mathbf{𝐀}\in {\mathbb{\mathbb{Z}}}_q^{n\times m}$. The normal form version of SIS is often used to reduce public key sizes by size $n$ as the static part of the matrix, the identity matrix ${\mathbf{𝐈}}_n$, can be omitted for data transmission.

A SIS instance can be reduced to a NFSIS instance if the first $n$ columns of its challenge matrix $\mathbf{𝐀}$ are invertible over ${\mathbb{\mathbb{Z}}}_q$. Assuming this is the case, denote the first $n$ columns of $\mathbf{𝐀}$ by ${\mathbf{𝐀}}_0$ and define the NFSIS challenge matrix by ${\mathbf{𝐀}}_0^{-1}\cdot \mathbf{𝐀}$. Then, any solution of the NFSIS instance is a solution of the SIS instance and vice versa.

Further versions

• SIS with infinity norm
• Decision SIS

Analysis of Assumption

The initial hardness results of Ajtai in 1996 were later refined by a series of works. All results follow are instances of the following theorem.

Theorem For any m = poly(n), any β > 0, and any sufficiently large q ≥ β · poly(n), solving SIS_n,m,,q,β with non-negligible probability is at least as hard as solving the decisional approximate shortest vector problem GapSVP_γ and the approximate shortest independent vectors problems SIVP_γ (among others) on arbitrary n-dimensional lattices (i.e., in the worst case) with overwhelming probability, for some γ = β · poly(n).

Constructions based on SIS

This is a non-exhaustive list of constructions, whose security is or can be based on SIS (or R-SIS and M-SIS).

• One-way function
• Collision-resistant hash function
• Preimage Sampleable Function
• Signatures
• Commitments
• Vector and Functional Commitments

Related Assumptions

• Approximate SIS
• Learning with Errors

Further reading suggestions

• Section 4.1 in "A decade of lattice cryptography" can help providing an intuition about SIS
• TODO - Discussion about NFSIS