Short Integer Solution

Short Integer Solution (SIS) is an average-case problem, which was introduced in 1996 by Miklós Ajtai.^[1] 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 $𝐀 \in ℤ_{q}^{n \times m}$ be chosen uniformly at random. An adversary is asked to find a short non-zero vector $𝐬 \in ℤ^{m}$ satisfying $𝐀 \cdot 𝐬 = 𝟎 mod q \land 0 < ‖ 𝐬 ‖ \leq β$ .

A solution to SIS without the condition $‖ 𝐬 ‖ \leq β$ can be found using Gaussian elimination. Thus, the condition $β < q$ is required as otherwise $(q, 0, \dots, 0) \in ℤ^{m}$ is a trivial solution.

ISIS_n,m,q,β - Inhomogeneous SIS `EQUIVALENT`

Let matrix $𝐀 \in ℤ_{q}^{n \times m}$ and target vector $𝐭 \in ℤ_{q}^{n}$ be chosen uniformly at random. An adversary is asked to find a short vector $𝐬 \in ℤ^{m}$ satisfying $𝐀 \cdot 𝐬 = 𝐭 mod q \land ‖ 𝐬 ‖ \leq β$ .

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

ISIS is as hard as SIS. A SIS instance can be reduced to ISIS using the last column of $𝐀$ as target vector for ISIS. Any solution $𝐬 \in ℤ^{m - 1}$ to the ISIS instance with challenge matrix $𝐀_{[1 : m - 1]}$ and target vector $𝐚_{m}$ yields a valid SIS solution $(𝐬^{T}, - 1) \in ℤ^{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 $𝐀$ .

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

Let matrix $\bar{𝐀} \in ℤ_{q}^{n \times m - n}$ be chosen uniformly at random and define $𝐀 = [\begin{matrix} 𝐈_{n} & \bar{𝐀} \end{matrix}]$ . An adversary is asked to find a short non-zero vector $𝐬 \in ℤ^{m}$ satisfying $𝐀 \cdot 𝐬 = 𝐭 mod q \land 0 < ‖ 𝐬 ‖ \leq β$ .

TODO

Analysis of Assumption

List of Reductions from other problems as well as cryptanalysis performed on SIS. Answer: Why is this problem hard to solve for a (quantum) computer / why should anyone believe that it is hard?

Constructions based on SIS

List of constructions built from SIS (with non-extensive list of citations)

Signatures
(Vector) Commitments

Related Assumptions

k-SIS
List of closely related assumptions - either because there is a reduction from

References

↑ Ajtai, Miklós. Generating hard instances of lattice problems. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996.

[1] Ajtai, Miklós. Generating hard instances of lattice problems. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996.

[1]

Formal Definition

SISn,m,q,β STANDARD

ISISn,m,q,β - Inhomogeneous SIS EQUIVALENT

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