Consider the following SIS problem: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $(R_q)^{r \times n}$=$\left(\mathbb{Z}_q[X]/(X^N+1)\right)^{r \times n}$ and $q$ a prime, it is hard to find a short element $s$ with some bounded norm $||s||\leq B$ s.t. $f_A(s)$=0. Is SIS still hard to solve when the polynomial modulus is a factor of $X^N+1$ instead of $X^N+1$ itself? Can you recommend any paper on this topic?

Consider the following hard problem: $f_{a,A}(s)$=$aAs$, where $a \in R_q$ is NON-invertible and public. The adversary is asked to find a short $a$ for a random $A$ as in the original SIS problem. It seems obvious if $a$ is invertible, then the hardness of this variant is equal to that of SIS, since if we can find a short $s$ such that $aAs$=0, then $s$ is the solution to $As$=0 when $a^{−1}$ is left-multiplied with both sides of this equation.

It seems $a$ is non-invertible implies that $gcd(a, X^N+1)$ is not 1 since $q$ is a prime. Assuming $gcd(a, X^N+1)$=$d$, then we have $\frac{a}{d}As=0\bmod(\frac{X^N+1}{d})$. Finding a $s$ for this equation is equal to solving the SIS problem with a polynomial modulus $\frac{X^N+1}{d}$. This is why I ask the above question. Thank you so much in advance.

  • $\begingroup$ The adversary must find a short $s$ or a short $a$? Additionally, $a$ is chosen uniformly at random from the set of non-invertible elements? $\endgroup$ May 8 '19 at 7:41
  • $\begingroup$ Answer to Vitor: To find a short $s$. $a$ is not a random element and public. $\endgroup$
    – user67451
    Jun 2 '19 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.