# Hardness of Short Interger Solution in Lattices

Short Integer Solution ($$SIS_{n,m,q,\beta}$$) is defined as:

Given a matrix $$A \in \mathbb{Z}_{q}^{n \times m}$$, find a non-zero vector $$x \in \mathbb{Z}^{m}$$ such that $$A \cdot x = 0\mod q$$ and $$||x|| \le \beta$$.

In the paper Trapdoors for hard lattices and new Cryptographic Constructions, SIS is proved to be hard by reducing standard worst-case lattice problem approx. SIVP to SIS i.e., if we solve a random instance of SIS, then any instance of approx. SIVP is solved.

In the paper On the complexity of computing short Linearly Independent Vectors and Short Bases in a lattice, approx. SIVP is proved to be NP-COMPLETE.

By this, can we say Short Integer Solution (SIS) problem in lattices is NP-Complete?

• Is SIVP reduced to SIS or is it approximate SIVP? – Florian Bourse May 14 '18 at 9:09

No, we cannot say that Short Integer Solution ($SIS$) problem is NP-Complete.
The results from those two papers are not directly related like that, because on the first one, the reduction is from $SIVP_\sqrt{n}$ to $SIS$ while in the second paper, $SIVP_c$ is proven to be NP-Hard for any constant $c$.
Until now, there is no proof that $SIVP_\sqrt{n}$ is NP-Hard and, since it has been proven to be in the intersection of NP and coNP, researchers believe that it is not NP-Hard.