Paper 2018/593

Ramanujan graphs in cryptography

Anamaria Costache, Brooke Feigon, Kristin Lauter, Maike Massierer, and Anna Puskas

Abstract

In this paper we study the security of a proposal for Post-Quantum Cryptography from both a number theoretic and cryptographic perspective. Charles-Goren-Lauter in 2006 proposed two hash functions based on the hardness of finding paths in Ramanujan graphs. One is based on Lubotzky--Phillips--Sarnak (LPS) graphs and the other one is based on Supersingular Isogeny Graphs. A 2008 paper by Petit-Lauter-Quisquater breaks the hash function based on LPS graphs. On the Supersingular Isogeny Graphs proposal, recent work has continued to build cryptographic applications on the hardness of finding isogenies between supersingular elliptic curves. A 2011 paper by De Feo-Jao-Plût proposed a cryptographic system based on Supersingular Isogeny Diffie--Hellman as well as a set of five hard problems. In this paper we show that the security of the SIDH proposal relies on the hardness of the SIG path-finding problem introduced in [CGL06]. In addition, similarities between the number theoretic ingredients in the LPS and Pizer constructions suggest that the hardness of the path-finding problem in the two graphs may be linked. By viewing both graphs from a number theoretic perspective, we identify the similarities and differences between the Pizer and LPS graphs.

Note: This revised version is now accepted for publication.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Research Directions in Number Theory: Women in Numbers IV, AWM Springer Series
Keywords
Post-Quantum Cryptographysupersingular isogeny graphsRamanujan graphs
Contact author(s)
klauter @ microsoft com
History
2018-12-19: revised
2018-06-12: received
See all versions
Short URL
https://ia.cr/2018/593
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/593,
      author = {Anamaria Costache and Brooke Feigon and Kristin Lauter and Maike Massierer and Anna Puskas},
      title = {Ramanujan graphs in cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2018/593},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/593}},
      url = {https://eprint.iacr.org/2018/593}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.