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,β

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$.

SIS intuitively states that it is hard to find a short vector in the kernel of matrix $\mathbf{𝐀}$.

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.

Ring-SIS_m,d,q,β

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

Let ${ℛ}$ denote a polynomial ring ${\mathbb{\mathbb{Z}}}_q[X]/(f(X))$. The function $f(X)$ is usually chosen as $(X^d+1)$ with special interest in $d$ being a power of 2. However, the Ring SIS (R-SIS) problem has also been studied for other choices such as $f(X)=(X^d-1)$.

Module-SIS_n,m,d,q,β

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

While M-SIS is a less compact variant of SIS than R-SIS, the M-SIS problem is asymptotically at least as hard as R-SIS and therefore gives a tighter bound on the hardness assumption of SIS. This makes assuming the hardness of M-SIS a safer, but less efficient underlying assumption when compared to R-SIS.

Versions of SIS

Inhomogeneous SIS_n,m,q,β

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 (ISIS) 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{𝐀}$.

Normal Form SIS_n,m,q,β

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 (NFSIS) 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

Hardness of SIS

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).

Similar reductions exist for R-SIS and M-SIS but their hardness relies on the worst-case hardness of SIVP over ideal and module lattices respectively. R-SIS as defined above is broken for cyclic lattices, i.e. ${ℛ}={\mathbb{\mathbb{Z}}}_q[X]/(X^d-1)$, but there are refined versions for cyclic lattices with worst-case to average-case reductions.

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 further intuition about SIS
• Lecture Notes by Vinod Vaikuntanathan
  • Lecture 3 on Smoothing Parameter and Worst-case to Average-case Reduction for SIS
  • Lecture 10 on Ideal Lattices and Ring Learning with Errors