k-SIS

The k-SIS assumption was introduced in 2011 by Boneh and Freeman. 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 $\mathbf{𝐀}\in {{ℛ}}_q^{n\times m}$ be chosen uniformly at random and $k$ hint vectors ${\mathbf{𝐬}}_i$ from $D_{{\mathrm{\Lambda }}_q^{\perp }(\mathbf{𝐀}),s}$ with $\Vert {\mathbf{𝐬}}_i\Vert$. Given $\mathbf{𝐀}$ and $\{{\mathbf{𝐬}}_i{\}}_{i\in [k]}$, an adversary is asked to find a new short non-zero vector ${\mathbf{𝐬}}^{*}\in {{ℛ}}^m$ satisfying ${𝒜}\cdot {\mathbf{𝐬}}^{*}=\mathbf{𝟎}modq\wedge \Vert {\mathbf{𝐬}}^{*}\Vert \le \beta \wedge {\mathbf{𝐬}}^{*}\notin {𝒦}-\text{span}(\{{\mathbf{𝐬}}_i{\}}_{i\in [k]}).$

The provided definition is the module-variant, which was defined by Albrecht et al. The original version can be recovered by setting ${ℛ}=\mathbb{\mathbb{Z}}$ and ${𝒦}=\mathbb{\mathbb{Q}}$.

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

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

Hardness of k-SIS

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

The initial proof relies on the following observation. Let $\mathbf{𝐀}\in {\mathbb{\mathbb{Z}}}_q^{n\times m-1},\mathbf{𝐞}\leftarrow D_{{\mathbb{\mathbb{Z}}}^{m-1},s}$, and $e_m$ a short ${\mathbb{\mathbb{Z}}}_q$-invertible entry. Define ${\mathbf{𝐀}}^{\prime }=\left[\begin{array}{cc}\mathbf{𝐀}& -\mathbf{𝐀}\cdot \mathbf{𝐞}\cdot e_m^{-1}\end{array}\right]$ and ${\mathbf{𝐞}}^{\prime }=\left[\begin{array}{c}\mathbf{𝐞}\\ e_m\end{array}\right]$. Then, ${\mathbf{𝐀}}^{\prime }\cdot {\mathbf{𝐞}}^{\prime }=\mathbf{𝐀}\cdot \mathbf{𝐞}-\mathbf{𝐀}\cdot \mathbf{𝐞}\cdot e_m^{-1}\cdot e_m=\mathbf{𝟎}.$ 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
• k-time GPV signatures in the standard model

Related Assumptions

• k-LWE