Source author record

Lisa Bromberg

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

1works
2topics
2close collaborators

Published work

1 publications

preprint2014arXiv

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

Cayley hash functions are based on a simple idea of using a pair of (semi)group elements, AA and BB, 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×22 \times 2 matrices over FpF_p. Since there are many known pairs of 2×22 \times 2 matrices over ZZ that generate a free monoid, this yields numerous pairs of matrices over FpF_p, for a sufficiently large prime pp, that are candidates for collision-resistant hashing. However, this trick can "backfire", and lifting matrix entries to ZZ may facilitate finding a collision. This "lifting attack" was successfully used by Tillich and Zémor in the special case where two matrices AA and BB generate (as a monoid) the whole monoid SL2(Z+)SL_2(Z_+). However, in this paper we show that the situation with other, "similar", pairs of matrices from SL2(Z)SL_2(Z) is different, and the "lifting attack" can (in some cases) produce collisions in the group generated by AA and BB, but not in the positive 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 SL2(Fp)SL_2(F_p).

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.