When does the SIS (Short Integer Solution) Lattice-problem start becoming easy (According to the parameters size)?

Question

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?

Answer 1

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)