2
$\begingroup$

I am new to lattice cryptography. May I ask why, if one has a trapdoor for SIS, i.e., can compute a short $x$ that satisfies $Ax=0$, then one can have a trapdoor for $Ax_{2}=y$? TIA

Improve this question
$\endgroup$
1
  • $\begingroup$ so is x^{2} just another x? not x squared? terrible notation. $\endgroup$
    – kodlu
    Commented Jul 12 at 5:20

1 Answer 1

Reset to default
4
$\begingroup$

A vector $x$ such that $Ax = 0 \pmod q$ is not a “trapdoor” by itself, it's just one solution to the SIS problem. Equivalently, it is a single short vector of the SIS lattice. Having this $x$ is not sufficient to solve arbitrary inhomogeneous SIS (ISIS) instances $Ax' = y \pmod q$.

If, instead, you have a short basis of the SIS lattice, then that does give you a trapdoor, and lets you solve ISIS instances, with the caveat that there is a gap (usually $\Omega(\sqrt{n})$) between the size of the short basis vectors and the size of the ISIS solutions.

Improve this answer
$\endgroup$

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