On cryptographic hash functions from arc-transitive graphs


cryptographic hash function
arc-transitive graph
triplet graph
sextet graph
expander graph
group word problem

How to Cite

Satake, S., & Jo, H. (2022). On cryptographic hash functions from arc-transitive graphs. Mathematical Cryptology, 2(1), 2–20. Retrieved from https://journals.flvc.org/mathcryptology/article/view/132124


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.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2022 Shohei Satake, Hyungrok Jo