Paper 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.

Note: More security evidence has been provided.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Cayley hash functions
Contact author(s)
shpilrain @ yahoo com
History
2016-02-02: last of 3 revisions
2015-07-21: received
See all versions
Short URL
https://ia.cr/2015/726
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/726,
      author = {Vladimir Shpilrain and Bianca Sosnovski},
      title = {Compositions of linear functions and applications to hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2015/726},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/726}},
      url = {https://eprint.iacr.org/2015/726}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.