Collision-free bounds for the BSV hash

Sandie Han, Ariane M. Masuda, Pragya Singh, Johann ThielarXiv 2017 · arXiv

Abstract

Let $L_u=\begin{bmatrix}1 & 0u & 1\end{bmatrix}$ and $R_v=\begin{bmatrix}1 & v0 & 1\end{bmatrix}$ be matrices in $SL_2(\mathbb Z)$ with $u, v\geq 1$. In 1991, Z\'emor developed a hash function based on $L_1$ and $R_1$. Recently, Bromberg, Shpilrain, and Vdovina proposed a hash function based on $L_u$ and $R_v$ when $u=v\in \{2,3\}$. For these values of $u$ and $v$, they analyzed the girth of the Cayley graph of the monoid generated by $L_u$ and $R_v$. As a consequence, they obtained lower bounds on the length of collisions for the corresponding hash functions. By using ideas from our previous work on $(u,v)$-Calkin-Wilf trees generated by $L_u$ and $R_v$, we extend their results for any $u, v\geq 1$.
BibTeX
@misc{han2017collision,
  author = {Sandie Han and Ariane M. Masuda and Pragya Singh and Johann Thiel},
  title = {{Collision-free bounds for the BSV hash}},
  year = {2017},
  eprint = {1703.02388},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1703.02388},
}

Loading related content...

Figure