Cryptology ePrint Archive: Report 2014/814

Navigating in the Cayley graph of $SL_2(F_p)$ and applications to hashing

Lisa Bromberg and Vladimir Shpilrain and Alina Vdovina

Abstract: Cayley hash functions are based on a simple idea of using a pair of (semi)group elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with $2 \times 2$ matrices over $F_p$. Since there are many known pairs of $2 \times 2$ matrices over $Z$ that generate a free monoid, this yields numerous pairs of matrices over $F_p$, for a sufficiently large prime $p$, that are candidates for collision-resistant hashing. However, this trick can ``backfire", and lifting matrix entries to $Z$ may facilitate finding a collision. This ``lifting attack" was successfully used by Tillich and Zémor in the special case where two matrices $A$ and $B$ generate (as a monoid) the whole monoid $SL_2(\Z_+)$. However, in this paper we show that the situation with other, ``similar", pairs of matrices from $SL_2(Z)$ is different, and the ``lifting attack" can (in some cases) produce collisions in the {\it group} generated by $A$ and $B$, but not in the positive {\it monoid}. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from $SL_2(F_p)$.

Category / Keywords: foundations / hash functions, Cayley graphs, Tillich-Zémor hash function

Date: received 8 Oct 2014

Contact author: shpilrain at yahoo com

Available format(s): PDF | BibTeX Citation

Version: 20141011:235554 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]