Let $q$ be a prime, $m,n$ be integers with $m>n$, and $\beta$ be a real number. Moreover, let $A$ be a matrix in $\mathbb Z^{n \times m}_q$. In the "short integer solution" (SIS) lattice problem, we are interested in non-zero integer vectors $\vec z \in \mathbb Z^m$ who satisfy two conditions:
- Solution: $A\vec z \equiv \vec0 \pmod{q}$
- Shortness: $\|\vec{z}\| \le \beta$
Note that for small-enough $\beta$'s, there might be no solution at all. Therefore, we will assume that $\beta$ is properly chosen to guarantee at least one solution.
For large values of $q$, there are worst-case lattice problems which reduce to the average-case SIS problem, and thereby establishing a firm ground for postulating that the SIS problem is hard-on-average (see, e.g., http://www.ecrypt.eu.org/wiki/index.php/Lattices#sis).
I'd like to know if there is any known result that postulates otherwise: Is it known that for $q=2$, the SIS problem is NOT hard-on-average? That is, by setting $q=2$, there's always an efficient algorithm which solves the SIS problem for random binary matrices $A \in \mathbb Z^{n \times m}_2$.
PS: I'm specially interested in the case where $q=2$, since it allows XOR operations instead of the less-efficient modular additions.
For $q=2$, one must have $\beta < 2$. However, such small $\beta$ does not guarantee an answer; see this question for more info.