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

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

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

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.

Ring-SIS_m,d,q,β

Let matrix $𝐚 \in ℛ_{q}^{m}$ be chosen uniformly at random. An adversary is asked to find a short non-zero vector $𝐬 \in ℛ^{m}$ satisfying $𝐚^{T} \cdot 𝐬 = 𝟎 mod q \land 0 < ‖ 𝐬 ‖ \leq β$ .

Let $ℛ$ denote a polynomial ring $ℤ_{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.^[2] However, the Ring SIS (R-SIS) problem has also been studied for other choices such as $f (X) = (X^{d} - 1)$ .^[3]^[4]^[5]

Module-SIS_n,m,d,q,β

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

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.^[6]

Versions of SIS

Inhomogeneous SIS_n,m,q,β

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

Normal Form SIS_n,m,q,β

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

Normal Form SIS (NFSIS) is related to the Hermite normal form of a uniformly random matrix $𝐀 \in ℤ_{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 $𝐈_{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 $𝐀$ are invertible over $ℤ_{q}$ . Assuming this is the case, denote the first $n$ columns of $𝐀$ by $𝐀_{0}$ and define the NFSIS challenge matrix by $𝐀_{0}^{- 1} \cdot 𝐀$ . Then, any solution of the NFSIS instance is a solution of the SIS instance and vice versa.

Further versions

SIS with infinity norm^[7]
Decision SIS^[7]

Hardness of SIS

The initial hardness results of Ajtai^[1] in 1996 were later refined by a series of works^[8]^[9]^[10]. All results follow are instances of the following theorem.

Theorem^[11] 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.^[2]^[6] R-SIS as defined above is broken for cyclic lattices, i.e. $ℛ = ℤ_{q} [X] / (X^{d} - 1)$ , but there are refined versions for cyclic lattices with worst-case to average-case reductions.^[3]^[4]^[5]

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^[1]
Collision-resistant hash function
Preimage Sampleable Function^[9]
Signatures^[7]^[9]^[12]
Commitments^[13]^[14]
Vector and Functional Commitments^[15]

Related Assumptions

References

↑ ^1.0 ^1.1 ^1.2 Ajtai, Miklós. Generating hard instances of lattice problems. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996.
↑ ^2.0 ^2.1 Lyubashevsky, Vadim, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. Annual international conference on the theory and applications of cryptographic techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010.
↑ ^3.0 ^3.1 Micciancio, Daniele. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.. IEEE, 2002.
↑ ^4.0 ^4.1 Peikert, Chris, and Alon Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. Theory of Cryptography Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.
↑ ^5.0 ^5.1 Lyubashevsky, Vadim, and Daniele Micciancio. Generalized compact knapsacks are collision resistant. International Colloquium on Automata, Languages, and Programming. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.
↑ ^6.0 ^6.1 Langlois, Adeline, and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography 75.3 (2015): 565-599.
↑ ^7.0 ^7.1 ^7.2 Lyubashevsky, Vadim. Lattice signatures without trapdoors. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.
↑ Micciancio, Daniele, and Oded Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM journal on computing 37.1 (2007): 267-302.
↑ ^9.0 ^9.1 ^9.2 Gentry, Craig, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. Proceedings of the fortieth annual ACM symposium on Theory of computing. 2008.
↑ Micciancio, Daniele, and Chris Peikert. Hardness of SIS and LWE with small parameters. Annual cryptology conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013.
↑ ^11.0 ^11.1 Peikert, Chris. A decade of lattice cryptography. Foundations and trends® in theoretical computer science 10.4 (2016): 283-424.
↑ Boyen, Xavier. Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more. International workshop on public key cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010.
↑ Baum, C., Damgård, I., Lyubashevsky, V., Oechsner, S. and Peikert, C. More efficient commitments from structured lattice assumptions. International conference on security and cryptography for networks. Cham: Springer International Publishing, 2018.
↑ Lyubashevsky, Vadim, Ngoc Khanh Nguyen, and Maxime Plançon. Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general. Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2022.
↑ Peikert, Chris, Zachary Pepin, and Chad Sharp. Vector and functional commitments from lattices. Theory of Cryptography Conference. Cham: Springer International Publishing, 2021.

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

[:4-2] 2.0 ^2.1 Lyubashevsky, Vadim, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. Annual international conference on the theory and applications of cryptographic techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010.

[:5-3] 3.0 ^3.1 Micciancio, Daniele. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.. IEEE, 2002.

[:6-4] 4.0 ^4.1 Peikert, Chris, and Alon Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. Theory of Cryptography Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.

[:7-5] 5.0 ^5.1 Lyubashevsky, Vadim, and Daniele Micciancio. Generalized compact knapsacks are collision resistant. International Colloquium on Automata, Languages, and Programming. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.

[:8-6] 6.0 ^6.1 Langlois, Adeline, and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography 75.3 (2015): 565-599.

[:1-7] 7.0 ^7.1 ^7.2 Lyubashevsky, Vadim. Lattice signatures without trapdoors. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.

[8] Micciancio, Daniele, and Oded Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM journal on computing 37.1 (2007): 267-302.

[:2-9] 9.0 ^9.1 ^9.2 Gentry, Craig, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. Proceedings of the fortieth annual ACM symposium on Theory of computing. 2008.

[10] Micciancio, Daniele, and Chris Peikert. Hardness of SIS and LWE with small parameters. Annual cryptology conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013.

[:3-11] 11.0 ^11.1 Peikert, Chris. A decade of lattice cryptography. Foundations and trends® in theoretical computer science 10.4 (2016): 283-424.

[12] Boyen, Xavier. Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more. International workshop on public key cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010.

[13] Baum, C., Damgård, I., Lyubashevsky, V., Oechsner, S. and Peikert, C. More efficient commitments from structured lattice assumptions. International conference on security and cryptography for networks. Cham: Springer International Publishing, 2018.

[14] Lyubashevsky, Vadim, Ngoc Khanh Nguyen, and Maxime Plançon. Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general. Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2022.

[15] Peikert, Chris, Zachary Pepin, and Chad Sharp. Vector and functional commitments from lattices. Theory of Cryptography Conference. Cham: Springer International Publishing, 2021.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Formal Definition

SISn,m,q,β

Ring-SISm,d,q,β

Module-SISn,m,d,q,β