Hash functions and Cayley graphs

Research paper by Gilles Zémor

Indexed on: 01 Jul '94Published on: 01 Jul '94Published in: Designs, Codes and Cryptography


We introduce cryptographic hash functions that are in correspondence with directed Cayley graphs, and for which finding collisions is essentially equivalent to finding short factorisations in groups. We show why having a large girth and a small diameter are properties that are relevant to hashing, and illustrate those ideas by proposing actual easily computable hash functions that meet those requirements.