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

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>ℓ</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-to-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>s</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-bit collision-resistance preserving hash function designed using <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> </mml:mrow> </mml:math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-to-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math>-bit compression function calls, we must have <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>⌈</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>−</mml:mo> <mml:mi>s</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>/</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mi>⌉</mml:mi> </mml:mrow> </mml:math>. Throughout the paper, all operations other than the compression function are assumed to be linear (which we call linear hash mode).