Better path-finding algorithms in LPS Ramanujan graphs

Eduardo Carvalho Pinto; Christophe Petit

doi:10.1515/jmc-2017-0051

Better path-finding algorithms in LPS Ramanujan graphs

Eduardo Carvalho Pinto, Christophe Petit

Computer Science

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

231 Downloads (Pure)

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.

Original language	English
Pages (from-to)	191-202
Number of pages	12
Journal	Journal of Mathematical Cryptology
Volume	12
Issue number	4
Early online date	20 Sept 2018
DOIs	https://doi.org/10.1515/jmc-2017-0051
Publication status	Published - 1 Dec 2018

Keywords

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

Access to Document

10.1515/jmc-2017-0051Licence: None: All rights reserved

Eduardo_Carvalho_Pinto_&_Christophe_Petit_Better_path_finding_algorithms_in_LPS_Ramanujan_graphs_Journal_of_Mathematical_Cryptology_2018
Checked for eligibility: 22/01/2019 This is the author accepted manuscript version of a paper published in the Journal of Mathematical Cryptology which can be found at: https://doi.org/10.1515/jmc-2017-0051
Accepted author manuscript, 386 KBLicence: None: All rights reserved

http://www.degruyter.com/view/j/jmc.2018.12.issue-4/jmc-2017-0051/jmc-2017-0051.xmlLicence: None: All rights reserved

Cite this

@article{630498adb79e407db996039b0be6f413,

title = "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 Charles-Goren-Lauter hash function.",

keywords = "Cryptography, Cayley graph, Tillich–Z{\'e}mor hash function, path finding algorithm",

author = "{Carvalho Pinto}, Eduardo and Christophe Petit",

year = "2018",

month = dec,

day = "1",

doi = "10.1515/jmc-2017-0051",

language = "English",

volume = "12",

pages = "191--202",

journal = "Journal of Mathematical Cryptology",

issn = "1862-2976",

publisher = "De Gruyter",

number = "4",

}

TY - JOUR

T1 - Better path-finding algorithms in LPS Ramanujan graphs

AU - Carvalho Pinto, Eduardo

AU - Petit, Christophe

PY - 2018/12/1

Y1 - 2018/12/1

N2 - 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.

AB - 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.

KW - Cryptography

KW - Cayley graph

KW - Tillich–Zémor hash function

KW - path finding algorithm

U2 - 10.1515/jmc-2017-0051

DO - 10.1515/jmc-2017-0051

M3 - Article

SN - 1862-2976

VL - 12

SP - 191

EP - 202

JO - Journal of Mathematical Cryptology

JF - Journal of Mathematical Cryptology

IS - 4

ER -

Better path-finding algorithms in LPS Ramanujan graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this