Paper 2021/1573

Improved Security Bound of \textsf{(E/D)WCDM}

Nilanjan Datta, Avijit Dutta, and Kushankur Dutta


In CRYPTO'16, Cogliati and Seurin proposed a block cipher based nonce based MAC, called {\em Encrypted Wegman-Carter with Davies-Meyer} (\textsf{EWCDM}), that gives $2n/3$ bit MAC security in the nonce respecting setting and $n/2$ bit security in the nonce misuse setting, where $n$ is the block size of the underlying block cipher. However, this construction requires two independent block cipher keys. In CRYPTO'18, Datta et al. came up with a single-keyed block cipher based nonce based MAC, called {\em Decrypted Wegman-Carter with Davies-Meyer} (\textsf{DWCDM}), that also provides $2n/3$ bit MAC security in the nonce respecting setting and $n/2$ bit security in the nonce misuse setting. However, the drawback of \textsf{DWCDM} is that it takes only $2n/3$ bit nonce. In fact, authors have shown that \textsf{DWCDM} cannot achieve beyond the birthday bound security with $n$ bit nonces. In this paper, we prove that \textsf{DWCDM} with $3n/4$ bit nonces provides MAC security up to $O(2^{3n/4})$ MAC queries against all nonce respecting adversaries. We also improve the MAC bound of \textsf{EWCDM} from $2n/3$ bit to $3n/4$ bit. The backbone of these two results is a refined treatment of extended mirror theory that systematically estimates the number of solutions to a system of bivariate affine equations and non-equations, which we apply on the security proofs of the constructions to achieve $3n/4$ bit security.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in FSE 2021
Wegman CarterExtended Mirror TheoryNonce Based MACEWCDMDWCDM.
Contact author(s)
nilanjan datta @ tcgcrest org
avirocks dutta13 @ gmail com
kushankur29 @ gmail com
2021-12-03: received
Short URL
Creative Commons Attribution


      author = {Nilanjan Datta and Avijit Dutta and Kushankur Dutta},
      title = {Improved Security Bound of \textsf{(E/D)WCDM}},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1573},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.