Better path-finding algorithms in LPS Ramanujan graphs

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • Ecole Polytechnique, Paris

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

Details

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

Keywords

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