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

Debasmita Chakraborty; Mridul Nandi

Paper 2024/1095

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

Debasmita Chakraborty

, Indian Statistical Institute, Kolkata, India

Mridul Nandi, Indian Statistical Institute, Kolkata, India

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 ℓ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: Preprint.
Keywords: Merkle-Damgård Merkle Tree Collision-Resistance Preserving Hash Compression Function.
Contact author(s): debasmitachakraborty1 @ gmail com
mridul nandi @ gmail com
History: 2024-07-05: approved; 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},
      note = {\url{https://eprint.iacr.org/2024/1095}},
      url = {https://eprint.iacr.org/2024/1095}
}