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 ($$\textsf {EWCDM}$$EWCDM) construction, as $$\textsf {E}_{K_2}\bigl (\textsf {E}_{K_1}(N)\oplus N\oplus \textsf {H}_{K_h}(M)\bigr )$$EK2(EK1(N)⊕N⊕HKh(M)) for a nonce N and a message M. This construction achieves roughly $$2^{2n/3}$$22n/3 bit MAC security with the assumption that $$\textsf {E}$$E is a PRP secure n-bit block cipher and $$\textsf {H}$$H is an almost xor universal n-bit hash function. In this paper we propose Decrypted Wegman-Carter with Davies-Meyer ($$\textsf {DWCDM}$$DWCDM) construction, which is structurally very similar to its predecessor $$\textsf {EWCDM}$$EWCDM except that the outer encryption call is replaced by decryption. The biggest advantage of $$\textsf {DWCDM}$$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$$K=K1=K2. Moreover, we can derive the hash key as $$K_h=\textsf {E}_K(1)$$Kh=EK(1), as long as $$|K_h|=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. $$\textsf {DWCDM}$$DWCDM is secure beyond the birthday bound, roughly up to $$2^{2n/3}$$22n/3 MAC queries and $$2^n$$2n verification queries against nonce-respecting adversaries. $$\textsf {DWCDM}$$DWCDM remains secure up to $$2^{n/2}$$2n/2 MAC queries and $$2^n$$2n 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
}