Paper 2024/1095
Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving Hash
, Indian Statistical Institute, Kolkata, IndiaAbstract
The collision-resistant hash function is an early cryptographic primitive that finds extensive use in various applications. Remarkably, the Merkle-Damgård and Merkle tree hash structures possess the collision-resistance preserving property, meaning the hash function remains collision-resistant when the underlying compression function is collision-resistant. This raises the intriguing question of whether reducing the number of underlying compression function calls with the collision-resistance preserving property is possible. In pursuit of addressing these inquiries, we prove that for an ℓn-to-sn-bit collision-resistance preserving hash function designed using r tn-to-n-bit compression function calls, we must have r ≥ ⌈(ℓ−s)/(t−1)⌉. Throughout the paper, all operations other than the compression function are assumed to be linear (which we call linear hash mode).
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published by the IACR in CIC 2024
- Keywords
- Merkle-DamgårdMerkle TreeCollision-Resistance Preserving HashCompression Function.
- Contact author(s)
-
debasmitachakraborty1 @ gmail com
mridul nandi @ gmail com - History
- 2024-09-18: last of 2 revisions
- 2024-07-05: received
- See all versions
- Short URL
- https://ia.cr/2024/1095
- License
-
CC0
BibTeX
@misc{cryptoeprint:2024/1095,
author = {Debasmita Chakraborty and Mridul Nandi},
title = {Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving Hash},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1095},
year = {2024},
url = {https://eprint.iacr.org/2024/1095}
}
