The Short integer solution problem is parameterized by four values:

  • $n$, the dimension of the vectors that must be added
  • $m$, the number of samples (dimension of the solution)
  • $\beta$, upper-bound for the length of the solution
  • $q$, the modulus defining $\mathbb{Z}_q$

Usually, the reductions from lattice problems to $SIS_{n, m, q, \beta}$ have the following template:

For any $m = poly(n)$ and $q \ge \beta \cdot \tilde{O}(\sqrt{n})$, solving $SIS_{n, m, q, \beta}$ gives a solution to an approximate version of a lattice problem with approximate factor $\gamma$ which is a function of $n$.

I was expecting something like that also for the ring version of SIS, namely, R-SIS, that works over a ring $R$ instead of $\mathbb{Z}$. However, on Peikert's survey on lattice crypto , in the end of section 4.3.4, some reductions from $SVP_\gamma$ to $R$-$SIS$ are cited, but no restriction on the values of $q$ are done.

So, do you know what are the lower bounds for $q$ in the reductions from lattice problems to $R$-$SIS$?


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.