Improved Security Bound of (E/D)WCDM

Authors

  • Nilanjan Datta Institute for Advancing Intelligence, TCG-CREST, Kolkata, India
  • Avijit Dutta Institute for Advancing Intelligence, TCG-CREST, Kolkata, India
  • Kushankur Dutta Institute for Advancing Intelligence, TCG-CREST, Kolkata, India

DOI:

https://doi.org/10.46586/tosc.v2021.i4.138-176

Keywords:

Wegman Carter, Extended Mirror Theory, Nonce Based MAC, EWCDM, DWCDM

Abstract

In CRYPTO’16, Cogliati and Seurin proposed a block cipher based nonce based MAC, called Encrypted Wegman-Carter with Davies-Meyer (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 Decrypted Wegman-Carter with Davies-Meyer (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 DWCDM is that it takes only 2n/3 bit nonce. In fact, authors have shown that DWCDM cannot achieve beyond the birthday bound security with n bit nonces. In this paper, we prove that DWCDM with 3n/4 bit nonces provides MAC security up to O(23n/4) MAC queries against all nonce respecting adversaries. We also improve the MAC bound of 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.

Downloads

Published

2021-12-03

Issue

Section

Articles

How to Cite

Improved Security Bound of (E/D)WCDM. (2021). IACR Transactions on Symmetric Cryptology, 2021(4), 138-176. https://doi.org/10.46586/tosc.v2021.i4.138-176