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

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?

• Can you define the acronyms you use, SIS, SIVP etc to make your post more readable. thanks. Jun 26, 2019 at 22:13
• Thanks for the remark I clarified the acronyms @kodlu Jun 27, 2019 at 8:00

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$$
(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)