International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Nilanjan Datta
Avijit Dutta
Mridul Nandi
Kan Yasuda
Download:
DOI: 10.1007/978-3-319-96884-1_21 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
Abstract: At CRYPTO 2016, Cogliati and Seurin have proposed a highly secure nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer (EWCDMEWCDM) construction, as EK2(EK1(N)⊕N⊕HKh(M))EK2(EK1(N)⊕N⊕HKh(M)) for a nonce N and a message M. This construction achieves roughly 22n/322n/3 bit MAC security with the assumption that EE is a PRP secure n-bit block cipher and HH is an almost xor universal n-bit hash function. In this paper we propose Decrypted Wegman-Carter with Davies-Meyer (DWCDMDWCDM) construction, which is structurally very similar to its predecessor EWCDMEWCDM except that the outer encryption call is replaced by decryption. The biggest advantage of DWCDMDWCDM is that we can make a truly single key MAC: the two block cipher calls can use the same block cipher key K=K1=K2K=K1=K2. Moreover, we can derive the hash key as Kh=EK(1)Kh=EK(1), as long as |Kh|=n|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. DWCDMDWCDM is secure beyond the birthday bound, roughly up to 22n/322n/3 MAC queries and 2n2n verification queries against nonce-respecting adversaries. DWCDMDWCDM remains secure up to 2n/22n/2 MAC queries and 2n2n verification queries against nonce-misusing adversaries.
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28854,
  title={Encrypt or Decrypt? To Make a Single-Key Beyond Birthday Secure Nonce-Based MAC},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={10991},
  pages={631-661},
  doi={10.1007/978-3-319-96884-1_21},
  author={Nilanjan Datta and Avijit Dutta and Mridul Nandi and Kan Yasuda},
  year=2018
}