# Hardness of $SIS$ and its reduction to an NP-complete problem

Short Integer Solution ($$SIS_\gamma^{(q,n,m,\beta)}$$): Given a matrix $$A\in Z_{q}^{n×m}$$, find $$x \in Z^m$$, such that $$Ax=0\mod q$$ and $$||x|| \le \beta$$

Is $$SIS\in NP$$ ?

If $$SIS \in NP$$, then it should be reduced to any NP-complete problem.

Is there any reduction from $$SIS$$ to a Hamiltonian cycle?

• Yes: the witness is such an x; it can be efficiently checked that it satisfies the conditions. The Cook-Levin theorem gives a reduction from any NP problem to SAT, which we know how to reduce to Hamiltonian cycle. – Chris Peikert Feb 17 '18 at 15:04
• @ChrisPeikert Could you maybe convert your comment to an answer? – Maarten Bodewes Oct 7 at 8:43