# Why does the following SIS-based decision language not make sense?

I'm currently reading about important lattices problems and noticed that while CVP, SVP, and LWE have decisional versions, SIS does not. I read in the question Relation between decisional SIS and leftover hash lemma in lattices that deciding between the distributions (A, u) when $$A \in Z_{q}^{n \times m}$$ and $$u = Ax$$ for some short x, versus the case that "u" is random is unfeasible because these distributions are statistically close.

However, what keeps us from looking on this language (which seems closely related to SIS to me), and ask how hard is it to decide it?

$$L_{m,n,\beta, q} = \{(A, u) \in Z_{q}^{n \times m}\times Z_{q}^{n}\,|\, \exists x \in Z_{q}^{m}: Ax = u \wedge ||x|| \leq \beta \}$$

This language seems well defined to me and in the case of $$\beta \leq q$$ it feels non-trivial too (looking on the first norm to keep the combinatorics simple - at most $$(\frac{\beta}{q})^{m}$$ of u's are in the language for each A...)

• But does deciding this language really helps to distinguish SIS samples from uniform ones? Even if $(A, u)$ is uniform, we will probably have $(A, u) \in L_{m, n, \beta, q}$. May 16 '19 at 9:44
• I think not. For example when choosing $q = 2^{m}$ and $\beta = \frac{q}{2}$, the number of legal u vectors will be $q^{m}$ but (at the first norm) the number of legal "x" (and as a result u for each A), is at most ${(\beta)}^{m}$ - a significantly smaller number, yet large enough so you have exponentially many options and the problem seems non-trivial. Am I missing something? May 16 '19 at 12:35
• The problem is trivial for such parameters, since the search version can be solved in polynomial time using LLL. Namely, applying LLL to the full-rank $m$-dimensional lattice $L := \{ z \in Z^m : Az = 0 \mod q \}$ gives us a vector $x$ such that $||x|| \le 2^{(m-1)/4}q^{n/m} = 2^{(m-1-4n)/4} < \beta = 2^{m-1}$. May 16 '19 at 13:07
• I think that for usual parameters, that is, the ones for which the theorem about the distributions apply, we must have $Pr[(A, u) \in L_{m,n,\beta,q}] \approx 1$ for uniform $(A, u)$, otherwise, we would have a lot of vectors $u$ that would not appear in the SIS samples and, then, the distributions would be very different. Maybe you could try to check if this is indeed the case... May 16 '19 at 13:13
• Regarding your second comment, I totally agree that the choice of $m, \beta, q$ for the regular SIS problem is such that this language will include uniform (A,u) w.h.p. . My question is why not choosing the parameters differently (i.e. - smaller $\beta$ that will make these distributions very different), and ask not which, but whether there is a witness x with this low weight. Is this question irrelevant or trivial? Because I expected to find papers that discuss this setting and found none... May 16 '19 at 13:36

More specifically, if A is non-singular, write it as $$A = [B | C]$$ with $$C$$ is square and invertible mod q, and set $$A' = C^{-1} A = [B' | I]$$. Then $$C^{-1} u = A' x = B' x_1 + x_2$$ where $$x = (x_1,x_2)$$ is small. Relabel $$s=x_1$$ and $$e=x_2$$.