Left-Right Cayley Hashing: A New Framework for Provably Secure Hash Functions

Abstract

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.