User:RobertHannah89/Sandbox

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

MD-compliant padding

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). Conditions:

• $|M|$ is a prefix of ${\mathsf {Pad}}(M)$.
• If $|M_{1}|=|M_{2}|$ then $|{\mathsf {Pad}}(M_{1})|=|{\mathsf {Pad}}(M_{2})|$.
• If $|M_{1}|\neq |M_{2}|$ then the last block of ${\mathsf {Pad}}(M_{1})$ is different from the last block of ${\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.