Approximate SIS

Approximate Short Integer Solution (SIS) is an assumption introduced in 2019 by Chen, Genise, and Mukherjee. It relaxes the conditions of SIS on the target vector by allowing a range of target vectors close to $\mathbf{𝟎}$.

Formal Definition

Approximate SIS_n,m,q,α,β STANDARD

Let matrix $\mathbf{𝐀}\in {\mathbb{\mathbb{Z}}}_q^{n\times m}$ be chosen uniformly at random. An adversary is asked to find a short non-zero vector $\mathbf{𝐬}\in {\mathbb{\mathbb{Z}}}^m$ satisfying $\mathbf{𝐀}\cdot \mathbf{𝐬}=\mathbf{𝐭}modq\wedge 0<\Vert \mathbf{𝐬}\Vert \le \beta \wedge \Vert \mathbf{𝐭}\Vert \le \alpha$.

Approximate SIS intuitively states that it is hard to find a short preimage of $\mathbf{𝐀}$ of a ball of target vectors surrounding $\mathbf{𝟎}$. Therefore, Approximate SIS can be seen as a specific multi-instance of ISIS, where the target vectors form a ball around $\mathbf{𝟎}$.

Versions of Approximate SIS

Chen, Genise, and Mukherjee introduce Approximate Inhomogeneous SIS and Approximate Normal Form ISIS in their paper and provide reductions to ISIS. We omit the definitions and reductions as they are combinations of versions of SIS and reduction techniques described in the linked article.

On the Hardness of Approximate SIS

Approximate SIS is at least as hard as normal form SIS. Any normal form SIS instance $\left[\begin{array}{cc}{\mathbf{𝐈}}_n& \overline{\mathbf{𝐀}}\end{array}\right]$ provides an approximate SIS instance $\overline{\mathbf{𝐀}}$. Any solution $(\mathbf{𝐬},\mathbf{𝐭})\in {\mathbb{\mathbb{Z}}}^{m-n}\times {\mathbb{\mathbb{Z}}}_q^n$ to the approximate SIS instance is a solution to the normal form SIS instance $\left[\begin{array}{c}-\mathbf{𝐭}\\ \mathbf{𝐬}\end{array}\right]\in {\mathbb{\mathbb{Z}}}^m$ of norm at most $\alpha +\beta$.

Chen et al. provide further reductions for the inhomogeneous version and its normal form from standard assumptions such as ISIS as well as LWE.

Constructions based on Approximate SIS

Approximate SIS was introduced in the context of approximate trapdoors. To reduce the dimensions of the gadget matrix $\mathbf{𝐆}={\mathbf{𝐈}}_n\otimes {\mathbf{𝐠}}^T$ introduced by Micciancio and Peikert in 2012, the gadget vector ${\mathbf{𝐠}}^T=\left[\begin{array}{ccccc}1& 2& 4& \dots & 2^{\lceil \log (q)\rceil }\end{array}\right]$ can be pruned by its smaller entries. This removes the possibility to generate a preimage of all exact targets, but still allows preimage sampling for vectors close to the target vector. Thus, almost any construction based on SIS can be adapted using Approximate SIS and using an approximate trapdoor is a common technique to optimise the efficiency of existing constructions.

Related Assumptions

• Short Integer Solution