6
$\begingroup$

SIS (Short Integer Solution) Problem : Given $m$ uniformly random vectors $a \in Z_q^n$, grouped as the columns of a matrix $A \in Z_q^{n.m}$, find a nonzero integer vector $z \in Z^m$ with $||z|| \leq \beta \lt q$, such that $Az = 0 \mod q$.

Concerning the hardness of the problem, there is a theorem that states that : for any $m = poly(n)$, $\beta \gt 0$, solving $SIS$ is at least as hard as solving other approximation problems like $GapSVP_\gamma$ (Decisional approximate Short Vector Problem) and $SIVP_\gamma$ (Short Independant Vector Problem) on arbitrary n-dimensional lattices, for some $\gamma = \beta.poly(n)$.

My question is : what are the maximum values of $\beta$ and $m$ relatively to $n$ for which the problem stays hard to solve? For example in the $GPV$ signatures they consider $m = 2n\log q$, and $\beta = 6n\log q$. But can we consider too $m = 4n\log q$? $8n\log q \dots $? $n^{100} \log q$? $\dots$ Same thing goes for $\beta$. What's the limit for these parameters for which the problem starts becoming easy?

$\endgroup$
  • $\begingroup$ Can you define the acronyms you use, SIS, SIVP etc to make your post more readable. thanks. $\endgroup$ – kodlu Jun 26 at 22:13
  • $\begingroup$ Thanks for the remark I clarified the acronyms @kodlu $\endgroup$ – abdul rahman taleb Jun 27 at 8:00
2
$\begingroup$

The problem becomes easy (as in `solvable in polynomial time') if $$\beta \geq \min_{k=1 \dots m} C^k \cdot q^{n/k}$$ for some constant $C$. This follows from:

  • volume $q^{n}$ for the $q$-ary kernel lattice
  • a Hermite approximation factor of $C^k$ for lattice reduction algorithms (LLL/BKZ) over a lattice of dimension $k$
  • noting that one can `ignore columns' to work with a lattice of dimension $k \leq m$

Some more details in Section 3 of

https://homepages.cwi.nl/~dadush/teaching/lattices-2018/notes/lecture-9.pdf

(where $C=\gamma_2$ because we just consider what is provable with LLL, but all other smaller fixed constants $C>1$ are also reachable in polynomial time)

$\endgroup$

Your Answer

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

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