User:RobertHannah89/Sandbox

This is denoted as ${\displaystyle \mathbf {Adv} _{SE}^{pr-cpa}(A)}$.

As mentioned in the introduction, the padding scheme used in the Merkle–Damgård construction must be chosen carefully to ensure the security of the scheme. Mihir Bellare gives sufficient conditions for a padding scheme to possess to ensure that the MD construction is secure: the scheme must be "MD-compliant" (the original length-padding scheme used by Merkle is an example of MD-compliant padding).[1]:145 Conditions:

• ${\displaystyle |M|}$ is a prefix of ${\displaystyle {\mathsf {Pad}}(M)}$.
• If ${\displaystyle |M_{1}|=|M_{2}|}$ then ${\displaystyle |{\mathsf {Pad}}(M_{1})|=|{\mathsf {Pad}}(M_{2})|}$.
• If ${\displaystyle |M_{1}|\neq |M_{2}|}$ then the last block of ${\displaystyle {\mathsf {Pad}}(M_{1})}$ is different from the last block of ${\displaystyle {\mathsf {Pad}}(M_{1})}$.

With these conditions in place, we find a collision in the MD hash function exactly when we find a collision in the underlying compression function. Therefore, the Merkle–Damgård construction is provably secure when the underlying compression function is secure. [1]:147

[1]

References

1. ^ a b c Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001