# How does the polynomial module impact the security of ring/lattices-based SIS problem?

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.

• 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? May 8 '19 at 7:41
• Answer to Vitor: To find a short $s$. $a$ is not a random element and public. Jun 2 '19 at 7:08