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

Question

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!

Answer 1

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.