\(k\)-SIS implied

Propose Edit

Updated:

The \(k\)-SIS assumption was introduced in 2011 by Boneh and Freeman [1]. The assumption hands out \(k\) hints additionally to the SIS challenge matrix, removing any linear combination of these hints from the solution space.

Definition

\(k\)-SIS\(_{n,m,q,\beta,s,\mathcal{R}}\)

Let matrix \(\mat{A} \in \mathcal{R}_q^{n \times m}\) be chosen uniformly at random and \(k\) hint vectors \(\vec{s}_i\) from \(D_{\Lambda_q^\perp(\mat{A}), s}\) with \(\norm{\vec{s}_i} \leq \beta\). Given \(\mat{A}\) and \(\set{\vec{s}_i}_{i \in [k]}\), an adversary is asked to find a new short non-zero vector \(\vec{s}^* \in \mathcal{R}^m\) satisfying

\[\mat{A} \cdot \vec{s}^* = \vec{0} \bmod q \land \norm{\vec{s}^*} \leq \beta \land \vec{s}^* \notin \mathcal{K}\text{-span}\left( \set{\vec{s}_i}_{i \in [k]} \right).\]

The provided definition is the module-variant, which was defined by Albrecht et al. [2]. The original version can be recovered by setting \(\mathcal{R} = \ZZ\) and \(\mathcal{K} = \QQ\).

Intuitively, \(k\)-SIS asks for a SIS solution that is not a linear combination of the provided hints. The condition \(\vec{s}^* \notin \mathcal{K}\text{-span}\left( \set{\vec{s}_i}_{i \in [k]} \right)\) can be dropped when \(k < m^{1/4}\) as then the probability that there is an additional short vector in the \(k\)-dimensional sublattice spanned by \(\set{\vec{s}_i}_{i \in [k]}\) is negligible [1].

Hardness

\(k\)-SIS\(_{n,m,q,\beta,s,\ZZ}\) is at least as hard as SIS\(_{n,m-k,q,\beta',\ZZ}\). Boneh and Freeman [1] proved this result for constant \(k \in \bigO{1}\) and Ling et al. [3] improved this result to \(k \in \bigO{m}\).

The initial proof [1] relies on the following observation. Let \(\mat{A} \in \ZZ_q^{n \times m}\), \(\vec{e} \sample D_{\ZZ^{m-1},s}\), and \(e_m\) a short \(\ZZ_q\)-invertible entry. Define \(\mat{A}' = \begin{bmatrix} \mat{A} &-\mat{A} \cdot \vec{e} \cdot e_m^{-1} \end{bmatrix}\) and \(\vec{e}' = (\vec{e}, e_m)\). Then, \(\mat{A}' \cdot \vec{e}' = \mat{A} \cdot \vec{e} - \mat{A} \cdot \vec{e} \cdot e_m^{-1} \cdot e_m = \vec{0}\). In this way, the proof embeds a hint for each added column to the challenge matrix. Embedding multiple hints and recovering a SIS solution requires several technical details, which we omit here.

A proof for the module-variant was provided in [4].

Constructions built from \(k\)-SIS

  • Linearly homomorphic signatures [1]
  • Standard model \(k\)-time GPV-signature [1]
  • Threshold Preimage Sampleable Function [5]
  • Threshold GPV-based Signature [5]
  • k-LWE can be seen as the dual or rather LWE version of \(k\)-SIS.

References

  • [1]Dan Boneh and David Mandell Freeman. 2011. Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures. In Public Key Cryptography - PKC 2011 - 14th International Conference on Practice and Theory in Public Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings (Lecture Notes in Computer Science), 2011. Springer, 1–16. Retrieved from https://ia.cr/2010/453
  • [2]Martin R. Albrecht, Valerio Cini, Russell W. F. Lai, Giulio Malavolta, and Sri Aravinda Krishnan Thyagarajan. 2022. Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable - (Extended Abstract). 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, 102–132. Retrieved from https://ia.cr/2022/941
  • [3]San Ling, Duong Hieu Phan, Damien Stehlé, and Ron Steinfeld. 2014. Hardness of k-LWE and Applications in Traitor Tracing. In Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I (Lecture Notes in Computer Science), 2014. Springer, 315–334. Retrieved from https://ia.cr/2014/494
  • [4]Martin R. Albrecht, Joël Felderhoff, Russell W. F. Lai, Oleksandra Lapiha, and Ivy K. Y. Woo. 2025. A Gaussian Leftover Hash Lemma for Modules over Number Fields. Retrieved from https://ia.cr/2025/1852
  • [5]Martin R. Albrecht, Russell W. F. Lai, Oleksandra Lapiha, and Ivy K. Y. Woo. 2025. Partial Lattice Trapdoors: How to Split Lattice Trapdoors, Literally. In Advances in Cryptology - ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, VIC, Australia, December 8-12, 2025, Proceedings, Part III (Lecture Notes in Computer Science), 2025. Springer, 265–296. Retrieved from https://ia.cr/2025/367