Paper 2017/473

Encrypted Davies-Meyer and Its Dual: Towards Optimal Security Using Mirror Theory

Bart Mennink and Samuel Neves


At CRYPTO 2016, Cogliati and Seurin introduced the Encrypted Davies-Meyer construction, $p_2(p_1(x) \oplus x)$ for two $n$-bit permutations $p_1,p_2$, and proved security up to $2^{2n/3}$. We present an improved security analysis up to $2^n/(67n)$. Additionally, we introduce the dual of the Encrypted Davies-Meyer construction, $p_2(p_1(x)) \oplus p_1(x)$, and prove even tighter security for this construction: $2^n/67$. We finally demonstrate that the analysis neatly generalizes to prove almost optimal security of the Encrypted Wegman-Carter with Davies-Meyer MAC construction. Central to our analysis is a modernization of Patarin's mirror theorem and an exposition of how it relates to fundamental cryptographic problems.

Note: Update based on ePrint 2017/579

Available format(s)
Publication info
Published by the IACR in CRYPTO 2017
PRP-to-PRFEncrypted Davies-MeyerEncrypted Davies-Meyer DualEWCDMoptimal security
Contact author(s)
b mennink @ cs ru nl
sneves @ dei uc pt
2017-06-20: last of 2 revisions
2017-05-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bart Mennink and Samuel Neves},
      title = {Encrypted Davies-Meyer and Its Dual: Towards Optimal Security Using Mirror Theory},
      howpublished = {Cryptology ePrint Archive, Paper 2017/473},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.