k-SIS: Difference between revisions

Latest revision as of 12:23, 29 August 2025

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 restricting the solution space by any linear combination of these hints.

Formal Definition

k-SIS_n,m,d,q,β,s

Let matrix $𝐀 \in ℛ_{q}^{n \times m}$ be chosen uniformly at random and $k$ hint vectors $𝐬_{i}$ from $D_{Λ_{q}^{⊥} (𝐀), s}$ with $‖ 𝐬_{i} ‖$ . Given $𝐀$ and ${𝐬_{i}}_{i \in [k]}$ , an adversary is asked to find a new short non-zero vector $𝐬^{*} \in ℛ^{m}$ satisfying $𝐀 \cdot 𝐬^{*} = 𝟎 mod q \land ‖ 𝐬^{*} ‖ \leq β \land 𝐬^{*} \notin 𝒦 - span ({𝐬_{i}}_{i \in [k]}) .$

The provided definition is the module-variant, which was defined by Albrecht et al.^[2] The original version can be recovered by setting $ℛ = ℤ$ and $𝒦 = ℚ$ .

Intuitively, k-SIS asks for a SIS solution that is not a linear combination of the provided hints.

The condition $𝐬^{*} \notin 𝒦 - span ({𝐬_{i}}_{i \in [k]})$ 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 ${𝐬_{i}}_{i \in [k]}$ is negligible.^[1]

Hardness of k-SIS

k-SIS_n,m,q,β,s (over $ℤ$ ) is at least as hard as SIS_n,m-k,q,β'. Boneh and Freeman^[1] proved this result for constant $k \in 𝒪 (1)$ and Ling et al.^[3] improved this result to $k \in 𝒪 (m)$ .

The initial proof^[1] relies on the following observation. Let $𝐀 \in ℤ_{q}^{n \times m - 1}, 𝐞 \leftarrow D_{ℤ^{m - 1}, s}$ , and $e_{m}$ a short $ℤ_{q}$ -invertible entry. Define $𝐀^{'} = [\begin{matrix} 𝐀 & - 𝐀 \cdot 𝐞 \cdot e_{m}^{- 1} \end{matrix}]$ and $𝐞^{'} = [\begin{matrix} 𝐞 \\ e_{m} \end{matrix}]$ . Then, $𝐀^{'} \cdot 𝐞^{'} = 𝐀 \cdot 𝐞 - 𝐀 \cdot 𝐞 \cdot e_{m}^{- 1} \cdot e_{m} = 𝟎 .$ 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.

No proof was provided for the module variant.

Constructions based on k-SIS

Linearly homomorphic signatures^[1]
k-time GPV signatures in the standard model^[1]

Related Assumptions

k-LWE

References

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Boneh, Dan, and David Mandell Freeman. Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. International Workshop on Public Key Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011.
↑ Albrecht, M.R., Cini, V., Lai, R.W., Malavolta, G. and Thyagarajan, S.A. Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable. Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2022.
↑ Ling, S., Phan, D.H., Stehlé, D. and Steinfeld, R. Hardness of k-LWE and applications in traitor tracing. Algorithmica 79.4 (2017): 1318-1352.

[:0-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Boneh, Dan, and David Mandell Freeman. Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. International Workshop on Public Key Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011.

[2] Albrecht, M.R., Cini, V., Lai, R.W., Malavolta, G. and Thyagarajan, S.A. Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable. Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2022.

[3] Ling, S., Phan, D.H., Stehlé, D. and Steinfeld, R. Hardness of k-LWE and applications in traitor tracing. Algorithmica 79.4 (2017): 1318-1352.

[1]

[2]

[3]

@@ Line 4: / Line 4: @@
 === k-SIS<sub>n,m,d,q,β,s</sub> ===
-Let matrix <math>\mathbf{A} \in \mathcal{R}_q^{n \times m}</math> be chosen uniformly at random and <math>k</math> hint vectors <math>\mathbf{s}_i</math> from <math>D_{\Lambda_q^\perp(\mathbf{A}), s}</math> with <math>\lVert \mathbf{s}_i \rVert</math>. Given <math>\mathbf{A}</math> and <math>\{ \mathbf{s}_i \}_{i \in [k]}</math>, an adversary is asked to find a new short non-zero vector <math>\mathbf{s}^* \in \mathcal{R}^m</math> satisfying <math>\mathcal{A} \cdot \mathbf{s}^* = \mathbf{0} \bmod q \land \lVert \mathbf{s}^* \rVert \leq \beta \land \mathbf{s}^* \notin \mathcal{K}-\text{span}\left( \{ \mathbf{s}_i \}_{i \in [k]} \right).</math>
+Let matrix <math>\mathbf{A} \in \mathcal{R}_q^{n \times m}</math> be chosen uniformly at random and <math>k</math> hint vectors <math>\mathbf{s}_i</math> from <math>D_{\Lambda_q^\perp(\mathbf{A}), s}</math> with <math>\lVert \mathbf{s}_i \rVert</math>. Given <math>\mathbf{A}</math> and <math>\{ \mathbf{s}_i \}_{i \in [k]}</math>, an adversary is asked to find a new short non-zero vector <math>\mathbf{s}^* \in \mathcal{R}^m</math> satisfying <math>\mathbf{A} \cdot \mathbf{s}^* = \mathbf{0} \bmod q \land \lVert \mathbf{s}^* \rVert \leq \beta \land \mathbf{s}^* \notin \mathcal{K}-\text{span}\left( \{ \mathbf{s}_i \}_{i \in [k]} \right).</math>
 The provided definition is the module-variant, which was defined by Albrecht et al.<ref>Albrecht, M.R., Cini, V., Lai, R.W., Malavolta, G. and Thyagarajan, S.A. [https://eprint.iacr.org/2022/941.pdf Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable]. ''Annual International Cryptology Conference''. Cham: Springer Nature Switzerland, 2022.</ref> The original version can be recovered by setting <math>\mathcal{R} = \mathbb{Z}</math> and <math>\mathcal{K} = \mathbb{Q}</math>.
-Intuitively, k-SIS asks for a SIS solution that is not a linear combination of the provided hints.
+Intuitively, k-SIS asks for a [[Short Integer Solution|SIS]] solution that is not a linear combination of the provided hints.
 The condition <math>\mathbf{s}^* \notin \mathcal{K}-\text{span}\left( \{ \mathbf{s}_i \}_{i \in [k]} \right) </math> can be dropped when <math>k < m^{1/4} </math> as then the probability that there is an additional short vector in the <math>k </math>-dimensional sublattice spanned by <math>\{ \mathbf{s}_i \}_{i \in [k]}</math> is negligible.<ref name=":0" />
@@ Line 26: / Line 26: @@
 == Related Assumptions ==
-* k-LWE
+* [[k-LWE]]
 == References ==
 <references />