Paper 2014/814

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

Lisa Bromberg, 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)$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
hash functionsCayley graphsTillich-Zémor hash function
Contact author(s)
shpilrain @ yahoo com
History
2014-10-11: received
Short URL
https://ia.cr/2014/814
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/814,
      author = {Lisa Bromberg and Vladimir Shpilrain and Alina Vdovina},
      title = {Navigating in the Cayley graph of $SL_2(F_p)$ and applications to hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2014/814},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/814}},
      url = {https://eprint.iacr.org/2014/814}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.