Find collision in Ajtai's hash function using short vector Background

What is Ajtai's hash function?

Given a matrix $A \hookleftarrow U(\mathbb{Z}_q^{n \times m})$ and a column vector $\vec{m} \in \mathbb{Z}_d^m$, the hash of the message $\vec{m}$ is given by

$H(\vec{m}) = A\vec{m} \mod q$

Ajtai's SIS-lattice

The corresponding lattice for $A$ denoted by $L^{\bot}(A)$ is defined as all vectors $\vec{v}$ such that $A\vec{v}=\vec{0}$, in other words $L^{\bot}(A)$ is the kernel of $A$. Thus as far as I understand, to find a basis for $L^{\bot}(A)$ is essentially equal to finding a basis for the kernel of $A$.

The SIS-problem

The $\beta$-SIS problem is the problem of finding a non-zero vector $\vec{v}$ such that $A\vec{v}=\vec{0}$ and $\|\vec{v}\|\le \beta$. This problem is known to be hard.

Is the hash function collision resistant?

Finding a collision for the hash function is as hard as solving the $2d\sqrt{m}$ SIS-problem. That means, given a collision $(\vec{x}, \vec{y})$ we can easily compute a short vector in $L^{\bot}(A)$ as $\vec{x}-\vec{y}$.

Why does it work? We have a collision, i.e $A\vec{x}=A\vec{y} \rightarrow A(\vec{x}-\vec{y})=\vec{0}$, so the vector $\vec{v}=\vec{x}-\vec{y}$ is in the lattice. Next, due to triangle inequality we have that $\|\vec{v}\| \le \|\vec{x}\|+\|\vec{y}\|$. Since both $\|x\|_{\infty} \le d$ and $\|y\|_{\infty} \le d$, it follows that $\|\vec{v}\| \le 2d\sqrt{m}$.

Question

Now, my question is; is it possible to go the other way around? That is, is it possible to find a collision for Ajtai's hash function given a short non-zero vector found e.g using Lentra-Lenstra-Lovász lattice reduction algorithm?
It depends on the exact domain of the hash function and the quality of the SIS solution, i.e., its norm (and the choice of norm itself).

Suppose the hash domain is $\{-d, \ldots, d\}^m$, i.e., vectors of $\ell_\infty$ norm at most $d$. Then any nonzero vector in Ajtai's lattice having Euclidean norm at most $d$ collides with the all-zeros input. (Actually, $\ell_\infty$ norm at most $d$ suffices.) Thus, finding short enough lattice vectors yields collisions.

But now suppose $d=1$, say. (This is a typical choice.) For standard parameters, the shortest (in Euclidean norm) nonzero vectors in Ajtai's lattice have norm about $\sqrt{n \log q} \gg d = 1$.  Thus, short vectors in Euclidean norm (which is what typical lattice-basis reduction algorithms deliver) may not be sufficient to yield a collision.  Instead, finding a collision requires finding a shortest nonzero vector in the $\ell_\infty$ norm. But little is known about lattice-basis reduction algorithms for this setting.

More details on these issues can be found, e.g., in the paper "SWIFFT: A Modest Proposal for FFT Hashing" (I am a coauthor).