k-SIS standard

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]

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