The following is an excerpt of a recent paper on lattice cryptography:
Let $n$ and $q$ be integers [...], and let $\beta > 0$ . Given a uniformly random matrix $A \in \mathbb Z^{n \times m}_q$ for some $m > n$ , the goal is to find a nonzero integer vector $\mathbf z \in \mathbb Z^m$ such that $A\mathbf z = 0 \bmod q$ and $\|\mathbf z\| \le \beta$ (where $\|\cdot\|$ denotes Euclidean norm). Observe that $\beta$ should be set large enough to ensure that a solution exists (e.g., $\beta > \sqrt{n \log q}$ suffices), but that $\beta \ge q$ makes the problem trivially easy to solve.
I'd like to know the reasoning behind the last statement:
- Why does $\beta > \sqrt{n \log q}$ guarantee the existence of a solution?
- Why does $\beta \ge q$ make the problem trivially easy to solve? What is the algorithm which outputs the answer?
Edit: Found the answer for my second question. For $i \in \{1,\ldots,m\}$, let $\mathbf{e_i} \in \mathbb Z^m$ be the $i$th unit vector (i.e. $\mathbf{e_i}$ is zero everwhere, except at the $i$th position, where it is 1). Then, for any $i \in \{1,\ldots,m\}$, the vector $\mathbf z = q\mathbf{e_i}$ is a solution to $A\mathbf z = 0 \bmod q$ satisfying $\|\mathbf z\| \le q$.