On cryptographic hash functions from arc-transitive graphs

Abstract

A cryptographic hash function is one of the fundamental objects as primitives in cryptography. Many attempts to realize an idealized hash function based on sophisticated mathematical structures are appearing in these days. One of the most successful suggestions for cryptographic hash functions is constructed from families of expander graphs proposed by Charles et al. (2006). It became the foundation stone of isogeny-based cryptography. In this paper we provide new cryptographic hash functions based on an arc-transitive graph, where its certain automorphisms play a central role to compute the hash value. We also discuss the security aspects, in particular, the collision-resistance relating to the group word problem, and deal with some explicit families of arc-transitive graphs, called triplet and sextet graphs, with large girth. In particular we prove that triplet and sextet graphs form new expanders.