k-SIS: Difference between revisions

Revision as of 10:12, 26 July 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 6: / Line 6: @@
 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>
-The provided definition is the module-variant, which was defined by Albrecht et al.<ref>Albrecht, Martin R., et al. [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>.
+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.
+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" />
 == Hardness of k-SIS ==
-k-SIS (over <math>\mathbb{Z}</math>) is at least as hard as SIS. Boneh and Freeman<ref name=":0" /> proved this result for constant <math>k \in \mathcal{O}(1)</math> and Ling et al.<ref>Ling, S., Phan, D.H., Stehlé, D. and Steinfeld, R. [https://www.iacr.org/archive/crypto2014/86160136/86160136.pdf Hardness of k-LWE and applications in traitor tracing]. ''Algorithmica'' 79.4 (2017): 1318-1352.</ref> improved this result to <math>k \in \mathcal{O}(m)</math>.
+k-SIS<sub>n,m,q,β,s</sub> (over <math>\mathbb{Z}</math>) is at least as hard as SIS<sub>n,m-k,q,β'</sub>. Boneh and Freeman<ref name=":0" /> proved this result for constant <math>k \in \mathcal{O}(1)</math> and Ling et al.<ref>Ling, S., Phan, D.H., Stehlé, D. and Steinfeld, R. [https://www.iacr.org/archive/crypto2014/86160136/86160136.pdf Hardness of k-LWE and applications in traitor tracing]. ''Algorithmica'' 79.4 (2017): 1318-1352.</ref> improved this result to <math>k \in \mathcal{O}(m)</math>.
+The initial proof<ref name=":0" /> relies on the following observation. Let <math>\mathbf{A} \in \mathbb{Z}_q^{n \times m-1}, \mathbf{e} \leftarrow D_{\mathbb{Z}^{m-1}, s}</math>, and <math>e_m</math> a short <math>\mathbb{Z}_q</math>-invertible entry. Define <math>\mathbf{A}' = \begin{bmatrix} \mathbf{A} &-\mathbf{A} \cdot \mathbf{e} \cdot e_m^{-1} \end{bmatrix}</math> and <math>\mathbf{e}' = \begin{bmatrix} \mathbf{e} \\ e_m \end{bmatrix}</math>. Then, <math>\mathbf{A}' \cdot \mathbf{e}' = \mathbf{A} \cdot \mathbf{e} -\mathbf{A} \cdot \mathbf{e} \cdot e_m^{-1} \cdot e_m = \mathbf{0}.</math> 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.
-TODO - Provide intuition of reduction
+No proof was provided for the module variant.
 == Constructions based on k-SIS ==
 * Linearly homomorphic signatures<ref name=":0" />
+* k-time GPV signatures in the standard model<ref name=":0" />
 == Related Assumptions ==