International Association
for Cryptologic Research

Cayley hash functions are based on a simple idea of using a pair of

(semi)group elements, A and B, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with linear functions of one variable over F_p. The corresponding hash functions are very efficient, in particular, due to the fact that a linear function is determined by its values at two points. Thus, we show that hashing a bit string of length $n$ with our method requires just 2n multiplications in F_p, but with particular pairs of linear functions that we suggest, one does not need to perform any multiplications at all. We also give explicit lower bounds on the

length of collisions for hash functions corresponding to these particular pairs of linear functions over F_p.