Full cryptanalysis of hash functions based on cubic Ramanujan graphs

Hyungrok Jo, Christophe Petit, Tsuyoshi Takagi

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Cayley hash functions are a family of cryptographic hash functions constructed from Cayley graphs, with appealing properties such as a natural parallelism and a security reduction to a clean, well-defined mathematical problem. As this problem involves non-Abelian groups, it is a priori resistant to quantum period finding algorithms and Cayley hash functions may therefore be a good foundation for post-quantum cryptography. Four particular parameter sets for Cayley hash functions have been proposed in the past, and so far dedicated preimage algorithms have been found for all of them. These algorithms do however not seem to extend to generic parameters, and as a result it is still an open problem to determine the security of Cayley hash functions in general. In this paper, we study the case of Chiu's Ramanujan graphs. We design a polynomial time preimage attack against the resulting Cayley hash function, showing that these particular parameters like the previous ones are not suitable for the construction. We extend our attacks on hash functions based on similar Cayley graphs as Chiu's Ramanujan graphs. On the positive side, we then suggest some possible ways to construct the Cayley hashes that may not be affected by this type of attacks. Our results contribute to a better understanding of the hard problems underlying the security of Cayley hash functions.

Original languageEnglish
Pages (from-to)1891-1899
Number of pages9
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number9
Publication statusPublished - Sept 2017

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Full cryptanalysis of hash functions based on cubic Ramanujan graphs'. Together they form a unique fingerprint.

Cite this