Paper 2024/233
Cayley hashing with cookies
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 $2\times 2$ matrices over $F_p$.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- hash functionCayley hashingrandom 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},
note = {\url{https://eprint.iacr.org/2024/233}},
url = {https://eprint.iacr.org/2024/233}
}
