Better path-finding algorithms in LPS Ramanujan graphs

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.

Keywords

• cryptography
• cayley graph
• tillich–zémor hash function
• path finding algorithm
• 94a60
• 11y50
• 05c12
• 05c25
• 08a50