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.

Hardness of k-SIS

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

TODO - Provide intuition of reduction

Constructions based on k-SIS

• Linearly homomorphic signatures

Related Assumptions

• k-LWE