IACR News item: 05 July 2024
Debasmita Chakraborty, Mridul Nandi
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).
Additional news items may be found on the IACR news page.