2
$\begingroup$

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...)

Improve this question
$\endgroup$
5
  • $\begingroup$ 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}$. $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented May 16, 2019 at 9:44
  • $\begingroup$ 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? $\endgroup$
    – Bartolinio
    Commented May 16, 2019 at 12:35
  • $\begingroup$ 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}$. $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented May 16, 2019 at 13:07
  • 1
    $\begingroup$ 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... $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented May 16, 2019 at 13:13
  • $\begingroup$ 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... $\endgroup$
    – Bartolinio
    Commented May 16, 2019 at 13:36

1 Answer 1

Reset to default
1
$\begingroup$

This is equivalent to an LWE language.

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks... this answer is really helpful! $\endgroup$
    – Bartolinio
    Commented May 19, 2019 at 7:55
  • $\begingroup$ More generally, this transformation always make LWE and SIS `syntactically equivalent': the true difference between LWE and SIS is not in how we write it, but how are its parameters; For SIS the parameters are such that (many) solutions always exists (its a dense problem), while for LWE, the solution shouldn't exist if the instance was random (its a sparse problem): a solution only exists because planted it. $\endgroup$
    – LeoDucas
    Commented May 19, 2019 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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