Welcome to the resource topic for 2014/814
Title:
Navigating in the Cayley graph of SL_2(F_p) and applications to hashing
Authors: Lisa Bromberg, Vladimir Shpilrain, 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).
ePrint: https://eprint.iacr.org/2014/814
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .