4
$\begingroup$

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 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 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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.