Cryptology ePrint Archive: Report 2018/500

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:

[ Cryptology ePrint archive ]