Better path-finding algorithms in LPS Ramanujan graphs

DOI10.1515/jmc-2017-0051zbMath1420.94045OpenAlexW2889941858WikidataQ62047234 ScholiaQ62047234MaRDI QIDQ1755951

Eduardo Carvalho Pinto, Christophe Petit

Publication date: 11 January 2019

Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)

Full work available at URL: http://pure-oai.bham.ac.uk/ws/files/57179283/better_path_finding.pdf

zbMATH Keywords

Cayley graphcryptographypath finding algorithmTillich-Zémor hash function

Mathematics Subject Classification ID

Cryptography (94A60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Uses Software

• Magma

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cryptographic hash functions from expander graphs
• Ramanujan graphs
• Growth and generation in \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\).
• Optimal ancilla-free Pauli+V circuits for axial rotations
• Expander graphs and their applications
• Full Cryptanalysis of LPS and Morgenstern Hash Functions
• Complexity of Strong Approximation on the Sphere
• Collisions for the LPS Expander Graph Hash Function
• Computing Modular Polynomials