# Using the Babai's Naive Rounding algorithm to decode, in the conditions of the SIS problem, is secure?

Given the SIS Problem: Given an integer q, a matrix $A \in \mathbb{Z}_q^ {n \times m}$ uniformly random, a real $\beta$, a syndrome $u \in \mathbb{Z}_q^n$, find a nonzero integer $e \in \mathbb{Z}^m$ such that $Ae=u \mod q$ and $|| e||_{2} \leq \beta$.

Sampling an uniform $A \in \mathbb{Z}_q^ {n \times m}$, along with a relatively short full-rank "trapdoor" set of vectors $S \in \Lambda^{\perp}(A)$ as in the paper of Ajtai of 1999 (Generating hard instances of the short basis problem). Choosing $t \in \mathbb{Z}^m$ via linear algebra such that $At=u \mod q$ and using the Babai naive rounding algorithm with basis $S$ to decode $-t \in \mathbb{Z}^m$ to a point $v \in \Lambda^{\perp}(A)$ yields the solution to the SIS problem $e=t+v$. Therefore it is difficult to obtain $e$ right?

But on the other hand doesn't the attack of Nguyen and Regev of the GGH scheme ( Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures ) work in this case? Is this a contradiction to the SIS hardness? I'm wrong somewhere!

• The Nguyen-Regev attack on GGH and NTRU works because those schemes were "leaking" the trapdoor S while signing. So after observing a certain number of signatures, their algorithm could recover S. So their attack had nothing to do with solving SIS, but rather with how to use the leaked information to recover a trapdoor (which can then be used to solve SIS). In the regular SIS problem, the S is unknown to the adversary and there is of course no "leakage" coming from anywhere. – Vadim L. Mar 25 '17 at 22:36
• @VadimL. As the user indicated it's considered an answer? Could you write it up as one? – Maarten Bodewes Mar 25 '17 at 23:45