International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving Hash

Authors:
Debasmita Chakraborty , Indian Statistical Institute
Mridul Nandi , Indian Statistical Institute
Download:
DOI: 10.62056/akgy11zn4
URL: https://cic.iacr.org//p/1/3/22
Search ePrint
Search Google
Abstract:

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 ${\ell}n$-to-$sn$-bit collision-resistance preserving hash function designed using $r$ $tn$-to-$n$-bit compression function calls, we must have $r \geq \lceil (\ell-s)/(t-1) \rceil $. Throughout the paper, all operations other than the compression function are assumed to be linear (which we call linear hash mode).

BibTeX
@article{cic-2024-34833,
  title={Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving Hash},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 3},
  url={https://cic.iacr.org//p/1/3/22},
  doi={10.62056/akgy11zn4},
  author={Debasmita Chakraborty and Mridul Nandi},
  year=2024
}