Cryptology ePrint Archive: Report 2015/726
Compositions of linear functions and applications to hashing
Vladimir Shpilrain and Bianca Sosnovski
Abstract: 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, we show that hashing a bit string of length n with our method requires, in general, at most 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.
Category / Keywords: Cayley hash functions
Date: received 20 Jul 2015, last revised 2 Feb 2016
Contact author: shpilrain at yahoo com
Available format(s): PDF | BibTeX Citation
Note: More security evidence has been provided.
Version: 20160202:131715 (All versions of this report)
Short URL: ia.cr/2015/726
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]