Cayley hash function is a significant cryptographic primitive known to be provably secure and expected to be universal due to the expansion property of Cayley graphs on finite groups. In this paper we propose a new Cayley-type hash function based on certain non-backtracking walks on an left-right Cayley complex. Then we discuss its collision-resistance and prove the universality, provided that the underlying complex is constructed from high-girth Cayley graph expanders. We also present instantiations of the proposed hash functions by using known explicit Cayley graph expanders on special linear groups over finite fields.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright (c) 2023 Yusuke Aikawa, Hyungrok Jo, Shohei Satake