3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Vadim L. Mar 25 '17 at 22:36
  • $\begingroup$ @VadimL. As the user indicated it's considered an answer? Could you write it up as one? $\endgroup$ – Maarten Bodewes Mar 25 '17 at 23:45
3
$\begingroup$

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.

$\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.