# 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?

• What research have you done? What have you tried? Where did you hit a problem? It would be cool if you‘ld edit you question accordingly. Don’t get me wrong, but we do expect you to do a significant amount of research before asking here – including searching this site for related Q&As that might shed light on your question. At worst it will help you frame a better question; at best it might even answer it. – e-sushi Apr 10 '16 at 14:00
• Unfortunately I haven't been able to come up with something that looks even close to a solution. What I've tried to do is solve the equation system with v=x-y and Ax=Ay but ending up with the zero vector. I also tried to combine the two shortest vectors in the LLL-reduced basis, but they don't hash to the same value (?) so it looks like a dead end to me. My lattice professor apparently thinks this is simple, I guess I've just overlooked something obvious. Hence the question. – user33284 Apr 11 '16 at 8:09
• Thanks for your edits – looks like a perfect question now! $(+1)$ – e-sushi Apr 11 '16 at 9:59
• I concur. I wish all questions were this nicely-written. – pg1989 Apr 13 '16 at 1:29

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.