Navigating in the Cayley graph of SL₂( F_p) and applications to hashing

DOI10.1007/S00233-015-9766-5MaRDI QIDQ2362747zbMATH OpenOpenAlexFDO

Authors Lisa Bromberg, Vladimir Shpilrain, Alina Vdovina

Publication date 14 July 2017

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4478

zbMATH Keywords

Cayley graphhash functionmatrix semigroup

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Cryptography (94A60)

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 $2imes2$ matrices over $F_p$. Since there are many known pairs of $2imes2$ 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'emor in the special case where two matrices $A$ and $B$ generate (as a monoid) the whole monoid $S{L}_2(Z_{+})$. However, in this paper we show that the situation with other, "similar", pairs of matrices from $S{L}_2(Z)$ is different, and the "lifting attack" can (in some cases) produce collisions in the group generated by $A$ and $B$, 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 $S{L}_2(F_p)$.

Recommendations

• Cryptographic Hash Functions and Some Applications to Information Security
• Recent developments in Cayley hash functions
• Hash functions and Cayley graphs
• Attacking the SL 2 hashing scheme
• A note on the hash function of Tillich and Zémor

Cites work

• \(\mathrm{SL}_2\) homomorphic hash functions: worst case to average case reduction and short collision search
• Cryptanalysis of the Tillich-Zémor hash function
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Growth and generation in \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\).
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• scientific article; zbMATH DE number 1917729 (Why is no real title available?)
• scientific article; zbMATH DE number 1406765 (Why is no real title available?)
• scientific article; zbMATH DE number 1456817 (Why is no real title available?)
• scientific article; zbMATH DE number 3045103 (Why is no real title available?)
• Preimages for the Tillich-Zémor hash function
• Rubik’s for Cryptographers
• Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).
• VSH, an Efficient and Provable Collision-Resistant Hash Function

Cited in

(17)

• Recent developments in Cayley hash functions
• New Zémor-Tillich type hash functions over \(\mathrm{GL}_2 (\mathbb{F}_{p^n})\)
• On the membership problem for some subgroups of \(SL_2(\mathbf{Z})\)
• Solving the membership problem for parabolic Möbius monoids
• \(\mathrm{SL}_2\) homomorphic hash functions: worst case to average case reduction and short collision search
• Compositions of linear functions and applications to hashing
• scientific article; zbMATH DE number 7498432 (Why is no real title available?)
• scientific article; zbMATH DE number 1917729 (Why is no real title available?)
• Security aspects of the Cayley hash function using discrete Heisenberg group
• On two-generator subgroups in \(\mathrm{SL}_2(\mathbb{Z})\), \(\mathrm{SL}_2(\mathbb{Q})\), and \(\mathrm{SL}_2(\mathbb{R})\)
• Navigating directed Cayley graphs of small diameter: a potent Solovay-Kitaev procedure
• Applications of finite non-abelian simple groups to cryptography in the quantum era
• Cryptanalysis of a Cayley hash function based on affine maps in one variable over a finite field
• Post-quantum hash functions using \(\operatorname{SL}_n (\mathbb{F}_p)\)
• Left-right Cayley hashing: a new framework for provably secure hash functions
• Cryptanalysis of TS-Hash
• Randomness and complexity in matrix groups

This page was built for publication: Navigating in the Cayley graph of \(\mathrm{SL}_2(\mathbb F_p)\) and applications to hashing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2362747)