Short Integer Solution (SIS) standard

Propose Edit

Updated:

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. SIS is one of the, if not the single most fundamental computational assumption in lattice-based cryptography, enabling the construction of any minicrypt [2] primitives such as collision-resistant hash functions, commitments, and unforgeable signatures.

Definition

SIS$_{n,m,q,\beta}$

Let matrix $\mat{A} \in \ZZ_q^{n \times m}$ be chosen uniformly at random. An adversary is asked to find a short non-zero vector $\vec{s} \in \ZZ_q^m$ satisfying $\mat{A} \cdot \vec{s} = \vec{0} \bmod q \land 0 < \norm{\vec{s}} \leq \beta$.

SIS intuitively states that it is hard to find a short vector in the kernel of matrix $\mat{A}$. A solution to SIS without the condition $\norm{\vec{s}} \leq \beta$ can be found using Gaussian elimination. Thus, the condition $\beta < q$ is required as otherwise $(q, 0, \dots, 0) \in \ZZ^m$ yields a trivial solution.

Ring-SIS$_{m,q,\beta,\mathcal{R}}$

Let matrix $\vec{a} \in \mathcal{R}_q^{m}$ be chosen uniformly at random. An adversary is asked to find a short non-zero vector $\vec{s} \in \mathcal{R}^{m}$ satisfying $\vec{a}^T \cdot \vec{s} = \vec{0} \bmod q \land 0 < \norm{\vec{s}} \leq \beta$.

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

Module-SIS$_{n,m,q,\beta,\mathcal{R}}$

Let matrix $\mat{A} \in \mathcal{R}_q^{n \times m}$ be chosen uniformly at random. An adversary is asked to find a short non-zero vector $\vec{s} \in \mathcal{R}^m$ satisfying $\mat{A} \cdot \vec{s} = \vec{0} \bmod q \land 0 < \norm{\vec{s}} \leq \beta$.

By using vectors/matrices over the ring $\mathcal{R}_q$, Module-SIS (M-SIS) [7] can be seen as a generalisation of SIS and R-SIS whose definitions can be recovered by setting $\mathcal{R} = \ZZ$ and $n=1$ respectively.

Variants

Inhomogeneous SIS$_{n,m,q,\beta}$

Let matrix $\mat{A} \in \ZZ_q^{n \times m}$ and target vector $\vec{t} \in \ZZ_q^n$ be chosen uniformly at random. An adversary is asked to find a short vector $\vec{s} \in \ZZ^m$ satisfying $\mat{A} \cdot \vec{s} = \vec{t} \bmod q \land \norm{\vec{s}} \leq \beta$.

The inhomogeneous version of SIS (ISIS) introduces a target vector $\vec{t} \in \ZZ_q^n$, which is chosen uniformly at random. The probability of ending up in the homogeneous case with $\vec{t} = \vec{0}$ happens with probability $q^{-n}$, which allows removing the condition $\vec{s} \neq \vec{0}$.

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

Normal Form SIS$_{n,m,q,\beta}$

Let matrix $\bar{\mat{A}} \in \ZZ_q^{n \times (m-n)}$ be chosen uniformly at random and define $\mat{A} = \begin{bmatrix} \mat{I}_n &\bar{\mat{A}} \end{bmatrix}$. An adversary is asked to find a short non-zero vector $\vec{s} \in \ZZ^m$ satisfying $\mat{A} \cdot \vec{s} = \vec{0} \bmod q \land 0 < \norm{\vec{s}} \leq \beta$.

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

Further Variants

  • SIS with infinity norm [8]
  • Decision SIS [8], which can be seen as a version of the leftover hash lemma.

Hardness

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

Theorem [12] For any $m = \poly{n}$, any $\beta > 0$, and any sufficiently large $q \geq \beta \cdot \poly{n}$, solving SIS$_{n,m,q,\beta}$ with non-negligible probability is at least as hard as solving the decisional approximate shortest vector problem GapSVP$_\gamma$ and the approximate shortest independent vectors problems SIVP$_\gamma$ (among others) on arbitrary n-dimensional lattices (i.e., in the worst case) with overwhelming probability, for some $\gamma = \beta \cdot \poly{n}$.

Similar reductions exist for R-SIS and M-SIS (over cyclotomic rings, i.e. $\mathcal{R} = \ZZ[X]/(X^d + 1)$ with $d$ a power of two) but their hardness relies on the worst-case hardness of SIVP over ideal and module lattices respectively [3][7]. R-SIS is broken for cyclic lattices, i.e. $\mathcal{R} = \ZZ[X]/(X^d - 1)$, but there are refined versions with worst-case to average-case reductions [4][5][6].

Constructions built from 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 [10]
  • Signatures [8][10][13]
  • Commitments [14][15]
  • Vector and functional commitments [16]

Further Reading Suggestions

  • Section 4.1 and 4.3 in A decade of lattice cryptography [12]
  • 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

References

  • [1]Miklós Ajtai. 1996. Generating Hard Instances of Lattice Problems (Extended Abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, 1996. ACM, 99–108. https://doi.org/10.1145/237814.237838
  • [2]Russell Impagliazzo. 1995. A Personal View of Average-Case Complexity. In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, June 19-22, 1995, 1995. IEEE Computer Society, 134–147. https://doi.org/10.1109/SCT.1995.514853
  • [3]Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On Ideal Lattices and Learning with Errors over Rings. In Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings (Lecture Notes in Computer Science), 2010. Springer, 1–23. Retrieved from https://ia.cr/2012/230
  • [4]Daniele Micciancio. 2002. Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions. In 43rd Symposium on Foundations of Computer Science, FOCS 2002, Vancouver, BC, Canada, November 16-19, 2002, Proceedings, 2002. IEEE Computer Society, 356–365. https://doi.org/10.1109/SFCS.2002.1181960
  • [5]Chris Peikert and Alon Rosen. 2006. Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings (Lecture Notes in Computer Science), 2006. Springer, 145–166. https://doi.org/10.1007/11681878_8
  • [6]Vadim Lyubashevsky and Daniele Micciancio. 2006. Generalized Compact Knapsacks Are Collision Resistant. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II (Lecture Notes in Computer Science), 2006. Springer, 144–155. https://doi.org/10.1007/11787006_13
  • [7]Adeline Langlois and Damien Stehlé. 2015. Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75, 3 (2015), 565–599. Retrieved from https://ia.cr/2012/090
  • [8]Vadim Lyubashevsky. 2012. Lattice Signatures without Trapdoors. In Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings (Lecture Notes in Computer Science), 2012. Springer, 738–755. Retrieved from https://ia.cr/2011/537
  • [9]Daniele Micciancio and Oded Regev. 2004. Worst-Case to Average-Case Reductions Based on Gaussian Measures. In 45th Symposium on Foundations of Computer Science, FOCS 2004, Rome, Italy, October 17-19, 2004, Proceedings, 2004. IEEE Computer Society, 372–381. https://doi.org/10.1109/FOCS.2004.72
  • [10]Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. 2008. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, 2008. ACM, 197–206. Retrieved from https://ia.cr/2007/432
  • [11]Daniele Micciancio and Chris Peikert. 2013. Hardness of SIS and LWE with Small Parameters. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I (Lecture Notes in Computer Science), 2013. Springer, 21–39. Retrieved from https://ia.cr/2013/069
  • [12]Chris Peikert. 2016. A Decade of Lattice Cryptography. Found. Trends Theor. Comput. Sci. 10, 4 (2016), 283–424. Retrieved from https://ia.cr/2015/939
  • [13]Xavier Boyen. 2010. Lattice Mixing and Vanishing Trapdoors: A Framework for Fully Secure Short Signatures and More. In Public Key Cryptography - PKC 2010, 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010. Proceedings (Lecture Notes in Computer Science), 2010. Springer, 499–517. https://doi.org/10.1007/978-3-642-13013-7_29
  • [14]Carsten Baum, Ivan Damgård, Vadim Lyubashevsky, Sabine Oechsner, and Chris Peikert. 2018. More Efficient Commitments from Structured Lattice Assumptions. In Security and Cryptography for Networks - 11th International Conference, SCN 2018, Amalfi, Italy, September 5-7, 2018, Proceedings (Lecture Notes in Computer Science), 2018. Springer, 368–385. Retrieved from https://ia.cr/2016/997
  • [15]Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Maxime Plançon. 2022. Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General. In Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part II (Lecture Notes in Computer Science), 2022. Springer, 71–101. Retrieved from https://ia.cr/2022/284
  • [16]Chris Peikert, Zachary Pepin, and Chad Sharp. 2021. Vector and Functional Commitments from Lattices. In Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part III (Lecture Notes in Computer Science), 2021. Springer, 480–511. Retrieved from https://ia.cr/2021/1254