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

Abstract

In CRYPTO 2016, Cogliati and Seurin have proposed a highly secure nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer (EWCDM) construction, as EK2(EK1(N)NHKh(M)) for a nonce N and a message M. This construction achieves roughly 22n/3 bit MAC security with the assumption that E is a PRP secure n-bit block cipher and H is an almost xor universal n-bit hash function. In this paper we propose Decrypted Wegman-Carter with Davies-Meyer (DWCDM) construction, which is structurally very similar to its predecessor EWCDM except that the outer encryption call is replaced by decryption. The biggest advantage of DWCDM is that we can make a truly single key MAC: the two block cipher calls can use the same block cipher key K=K1=K2. Moreover, we can derive the hash key as Kh=EK(1), as long as |Kh|=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. is secure beyond the birthday bound, roughly up to MAC queries and verification queries against nonce-respecting adversaries. remains secure up to MAC queries and verification queries against nonce-misusing adversaries.

Note: Minor Editorial Changes

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2018
Keywords
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
History
2018-06-08: last of 3 revisions
2018-05-25: received
See all versions
Short URL
https://ia.cr/2018/500
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/500,
      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},
      url = {https://eprint.iacr.org/2018/500}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.