Cayley hashing with cookies

Vladimir Shpilrain; Bianca Sosnovski

Paper 2024/233

Cayley hashing with cookies

Vladimir Shpilrain, The City College of New York

Bianca Sosnovski, Queensborough Community College, CUNY

Abstract

Cayley hash functions are based on a simple idea of using a pair of semigroup 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 semigroup. The main advantage of Cayley hash functions compared to, say, hash functions in the SHA family is that when an already hashed document is amended, one does not have to hash the whole amended document all over again, but rather hash just the amended part and then multiply the result by the hash of the original document. Some authors argued that this may be a security hazard, specifically that this property may facilitate finding a second preimage by splitting a long bit string into shorter pieces. In this paper, we offer a way to get rid of this alleged disadvantage and keep the advantages at the same time. We call this method ``Cayley hashing with cookies" using terminology borrowed from the theory of random walks in a random environment. For the platform semigroup, we use matrices over .

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: hash function Cayley hashing random walks
Contact author(s): shpilrain @ yahoo com
bsosnovski @ qcc cuny edu
History: 2024-02-16: approved; 2024-02-14: received; See all versions
Short URL: https://ia.cr/2024/233
License: CC BY

BibTeX

@misc{cryptoeprint:2024/233,
      author = {Vladimir Shpilrain and Bianca Sosnovski},
      title = {Cayley hashing with cookies},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/233},
      year = {2024},
      url = {https://eprint.iacr.org/2024/233}
}