Cryptology ePrint Archive: Report 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^{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.

Category / Keywords: PRP-to-PRF, Encrypted Davies-Meyer, Encrypted Davies-Meyer Dual, EWCDM, optimal security

Original Publication (in the same form): IACR-CRYPTO-2017

Date: received 26 May 2017, last revised 20 Jun 2017

Contact author: b mennink at cs ru nl, sneves@dei uc pt

Available format(s): PDF | BibTeX Citation

Note: Update based on ePrint 2017/579

Version: 20170620:161338 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]