Better path-finding algorithms in LPS Ramanujan graphs

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes

External organisations

  • Ecole Polytechnique, Paris


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 Charles-Goren-Lauter hash function.


Original languageEnglish
Pages (from-to)191-202
Number of pages12
JournalJournal of Mathematical Cryptology
Issue number4
Early online date20 Sep 2018
Publication statusPublished - 1 Dec 2018


  • Cryptography, Cayley graph, Tillich–Zémor hash function, path finding algorithm