Paper 2018/500

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

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


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.

Note: Minor Editorial Changes

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2018
$\textsf{EDM}$$\textsf{EWCDM}$Mirror TheoryExtended Mirror TheoryH-Coefficient
Contact author(s)
nilanjan_isi_jrf @ yahoo com
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
yasuda kan @ lab ntt co jp
2018-06-08: last of 3 revisions
2018-05-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nilanjan Datta and Avijit Dutta and Mridul Nandi and Kan Yasuda},
      title = {Encrypt or Decrypt? To Make a Single-Key Beyond Birthday Secure Nonce-Based MAC},
      howpublished = {Cryptology ePrint Archive, Paper 2018/500},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.