**Encrypt or Decrypt? To Make a Single-Key Beyond Birthday Secure Nonce-Based MAC**

*Nilanjan Datta and Avijit Dutta and Mridul Nandi and Kan Yasuda*

**Abstract: **In CRYPTO 2016, Cogliati and Seurin have proposed a highly secure nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer ($\textsf{EWCDM}$) construction, as $\textsf{E}_{K_2}\bigl(\textsf{E}_{K_1}(N)\oplus N\oplus \textsf{H}_{K_h}(M)\bigr)$ for a nonce $N$ and a message $M$. This construction achieves roughly $2^{2n/3}$ bit MAC security with the assumption that $\textsf{E}$ is a PRP secure $n$-bit block cipher and $\textsf{H}$ is an almost xor universal $n$-bit hash function. In this paper we propose Decrypted Wegman-Carter with Davies-Meyer ($\textsf{DWCDM}$) construction, which is structurally very similar to its predecessor $\textsf{EWCDM}$ except that the outer encryption call is replaced by decryption. The biggest advantage of $\textsf{DWCDM}$ is that we can make a truly single key MAC: the two block cipher calls can use the same block cipher key $K=K_1=K_2$. Moreover, we can derive the hash key as $K_h=\textsf{E}_K(1)$, as long as $|K_h|=n$. Whether we use encryption or decryption in the outer layer makes a huge difference; using the decryption instead enables us to apply an extended version of the mirror theory by Patarin to the security analysis of the construction. $\textsf{DWCDM}$ is secure beyond the birthday bound, roughly up to $2^{2n/3}$ MAC queries and $2^n$ verification queries against nonce-respecting adversaries. $\textsf{DWCDM}$ remains secure up to $2^{n/2}$ MAC queries and $2^n$ verification queries against nonce-misusing adversaries.

**Category / Keywords: **$\textsf{EDM}$, $\textsf{EWCDM}$, Mirror Theory, Extended Mirror Theory, H-Coefficient

**Original Publication**** (with major differences): **IACR-CRYPTO-2018

**Date: **received 22 May 2018, last revised 8 Jun 2018

**Contact author: **nilanjan_isi_jrf at yahoo com, avirocks dutta13@gmail com, mridul nandi@gmail com, yasuda kan@lab ntt co jp

**Available format(s): **PDF | BibTeX Citation

**Note: **Minor Editorial Changes

**Version: **20180608:081829 (All versions of this report)

**Short URL: **ia.cr/2018/500

[ Cryptology ePrint archive ]