Consider the following modification to the Short Integer Solution (SIS) problem:
Let $n$ be an integer and $\alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log \alpha)$ be functions of $n$. Sample a uniform $A\gets[-\alpha,\alpha]^{n\times m}$. The task is to compute "short" vector $e\in\mathbb{Z}^m$ in the kernel of $A$. That is:
- $|e| < \beta$.
- $A.e=0^n$. Here, equality holds over the integers
The usual version of SIS is the same as above, except where $A.e=0^n$ holds mod $q$, and $q=2\alpha+1$ (so that $A$ is uniform in $\mathbb{Z}_q^{n\times m}$). This variant removes the modulus.
Question: Are there any non-trivial hardness/easiness results for this version of SIS? What settings of parameters are easy, and which (if any) can be proved hard based on worse-case lattice problems, as in the usual version of SIS?
Trivial attack: There is an trivial algorithm in the case where $\beta$ is huge. You can compute a kernel vector over the integers by taking minors of the matrix $A$. These minors, and hence the kernel vector, can be easily upper bounded by $(\alpha n)^{O(n)}$. So in the regime $\beta= (\alpha n)^{O(n)}$, there is a trivial attack.
What I'm most curious about is the case where $\alpha,\beta$ are polynomial in $n$. Are there any attacks here, or can any hardness be shown?
I picked the distribution for $A$ above to give a concrete problem. But I'd also be interested in other distributions on $A$. For example, what if the entries of $A$ are discrete Gaussians, etc?
One can also consider an inhomogeneous version of this SIS variant, where $A.e=u$, for some vector $u$ (again, without a modulus). We have to be careful, though as for large $u$ there won't be a solution. Maybe we restrict to random $u\in\{0,1\}$, or in $[-\gamma,\gamma]^n$. I'd also be interested if anything can be said about this problem as well, besides the straightforward adaptation of the trivial attack from above.
