Better path-finding algorithms in LPS Ramanujan graphs
Eduardo Carvalho Pinto, Christophe Petit · Journal of Mathematical Cryptology · 2018
Abstract We provide a new heuristic polynomial time algorithm that computes short paths between arbitrary pairs of vertices in Lubotzky–Philipps–Sarnak’s Ramanujan graphs. The paths returned by our algorithm are shorter by a factor approximately 16/7 compared to previous work, and they are close to optimal for vertices corresponding to diagonal matrices. Our results also lead to an improved cryptanalysis of the Charles–Goren–Lauter hash function.