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

Bart Mennink; Samuel Neves

Paper 2017/473

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^{2 n / 3}$ . We present an improved security analysis up to $2^{n} / (67 n)$ . 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

Metadata

Available format(s): PDF
Publication info: Published by the IACR in CRYPTO 2017
Keywords: PRP-to-PRF Encrypted Davies-Meyer Encrypted Davies-Meyer Dual EWCDM optimal security
Contact author(s): b mennink @ cs ru nl
sneves @ dei uc pt
History: 2017-06-20: last of 2 revisions; 2017-05-28: received; See all versions
Short URL: https://ia.cr/2017/473
License: 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},
      url = {https://eprint.iacr.org/2017/473}
}