7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – e-sushi Apr 10 '16 at 14:00
  • 2
    $\begingroup$ 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. $\endgroup$ – user33284 Apr 11 '16 at 8:09
  • $\begingroup$ Thanks for your edits – looks like a perfect question now! $(+1)$ $\endgroup$ – e-sushi Apr 11 '16 at 9:59
  • $\begingroup$ I concur. I wish all questions were this nicely-written. $\endgroup$ – pg1989 Apr 13 '16 at 1:29
7
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.