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

Bart Mennink and Samuel Neves

##### Abstract

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
Keywords
PRP-to-PRFEncrypted Davies-MeyerEncrypted Davies-Meyer DualEWCDMoptimal security
Contact author(s)
b mennink @ cs ru nl
sneves @ dei uc pt
History
2017-06-20: last of 2 revisions
See all versions
Short URL
https://ia.cr/2017/473

CC BY

BibTeX

@misc{cryptoeprint:2017/473,
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{https://eprint.iacr.org/2017/473}},
url = {https://eprint.iacr.org/2017/473}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.