Short Integer Solution: Difference between revisions

Revision as of 14:07, 25 July 2025

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.

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^[2]
Decision SIS^[2]

Hardness of SIS

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

Theorem^[6] 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^[1]
Collision-resistant hash function
Preimage Sampleable Function^[4]
Signatures^[2]^[4]^[7]
Commitments^[8]^[9]
Vector and Functional Commitments^[10]

Related Assumptions

Approximate SIS
Learning with Errors

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 ^2.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.
↑ ^4.0 ^4.1 ^4.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.
↑ ^6.0 ^6.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, Carsten, et al. 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.

[:1-2] 2.0 ^2.1 ^2.2 Lyubashevsky, Vadim. Lattice signatures without trapdoors. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.

[3] 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-4] 4.0 ^4.1 ^4.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.

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

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

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

[8] Baum, Carsten, et al. More efficient commitments from structured lattice assumptions. International conference on security and cryptography for networks. Cham: Springer International Publishing, 2018.

[9] 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.

[10] 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]

@@ Line 12: / Line 12: @@
 == Versions of SIS ==
-=== ISIS<sub>n,m,q,β</sub> - Inhomogeneous SIS ===
+=== Inhomogeneous SIS<sub>n,m,q,β</sub> ===
 Let matrix <math>\mathbf{A} \in \mathbb{Z}_q^{n \times m}</math>and target vector <math>\mathbf{t} \in \mathbb{Z}_q^n</math> be chosen uniformly at random. An adversary is asked to find a short vector <math>\mathbf{s} \in \mathbb{Z}^m</math> satisfying <math>\mathbf{A} \cdot \mathbf{s} = \mathbf{t} \bmod q \land \lVert \mathbf{s} \rVert \leq \beta</math>.
-The inhomogeneous version of SIS introduces a target vector <math>\mathbf{t} \in \mathbb{Z}_q^n</math>, which is chosen uniformly at random. The probability of ending up in the homogeneous case with <math>\mathbf{t} = \mathbf{0}</math> happens with probability <math>q^{-n}</math>,  which allows removing the condition of <math>\mathbf{s}</math> being non-zero.
+The inhomogeneous version of SIS (ISIS) introduces a target vector <math>\mathbf{t} \in \mathbb{Z}_q^n</math>, which is chosen uniformly at random. The probability of ending up in the homogeneous case with <math>\mathbf{t} = \mathbf{0}</math> happens with probability <math>q^{-n}</math>,  which allows removing the condition of <math>\mathbf{s}</math> being non-zero.
 ISIS is as hard as SIS. A SIS instance can be reduced to ISIS using the last column of <math>\mathbf{A}</math> as target vector for ISIS. Any solution <math>\mathbf{s} \in \mathbb{Z}^{m-1}</math> to the ISIS instance with challenge matrix <math>\mathbf{A}_{[1:m-1]}</math> and target vector <math>\mathbf{a}_m</math> yields a valid SIS solution <math>(\mathbf{s}^T, -1) \in \mathbb{Z}^m</math> 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 <math>\mathbf{A}</math>.
-=== NFSIS<sub>n,m,q,β</sub> - Normal Form SIS ===
+=== Normal Form SIS<sub>n,m,q,β</sub> ===
 Let matrix <math>\bar{\mathbf{A}} \in \mathbb{Z}_q^{n \times m-n}</math> be chosen uniformly at random and define <math>\mathbf{A} = \begin{bmatrix} \mathbf{I}_n &\bar{\mathbf{A}} \end{bmatrix}</math>. An adversary is asked to find a short non-zero vector <math>\mathbf{s} \in \mathbb{Z}^m</math>satisfying <math>\mathbf{A} \cdot \mathbf{s} = \mathbf{t} \bmod q \land 0 < \lVert \mathbf{s} \rVert \leq \beta</math>.
-Normal Form SIS is related to the Hermite normal form of a uniformly random matrix <math>\mathbf{A} \in \mathbb{Z}_q^{n \times m}</math>. The normal form version of SIS is often used to reduce public key sizes by size <math>n</math> as the static part of the matrix, the identity matrix <math>\mathbf{I}_n</math>, can be omitted for data transmission.
+Normal Form SIS (NFSIS) is related to the Hermite normal form of a uniformly random matrix <math>\mathbf{A} \in \mathbb{Z}_q^{n \times m}</math>. The normal form version of SIS is often used to reduce public key sizes by size <math>n</math> as the static part of the matrix, the identity matrix <math>\mathbf{I}_n</math>, can be omitted for data transmission.
 A SIS instance can be reduced to a NFSIS instance if the first <math>n