Paper 2026/2428

Beyond-Birthday MAC Security for Encrypted Wegman-Carter and EWCDMD

Abstract

At CRYPTO 2016, Cogliati and Seurin proposed EWCDM as a nonce-based MAC construction making two block cipher calls and one almost-XOR-universal (AXU) hash evaluation and achieving beyond-birthday-bound (BBB) security. They noticed that a simplified variant of EWCDM named Encrypted Wegman--Carter (EWC) admits a birthday distinguishing attack. Later, at CRYPTO 2017, Mennink and Neves proposed EWCDMD, the dual of EWCDM, as a new candidate BBB-secure MAC, but at EUROCRYPT 2020 Nandi proposed a birthday distinguishing attack against EWCDMD. However, the distinguishing attacks did not yield forgeries, and whether EWC and EWCDMD have BBB unforgeability (or MAC security) remains open. We prove beyond-birthday unforgeability for EWC and EWCDMD and answer this long-standing open problem positively. Using an $n$-bit block cipher and an $O(2^{-n})$-AXU hash family, we prove that both constructions are secure up to $2^{5n/6}$ MAC queries and nearly $2^n$ verification queries, in the nonce-respecting setting. To bypass the birthday distinguishing attacks, our proofs directly analyze forgery events using auxiliary experiments indexed by hash values and messages. For EWC, we additionally employ conditional permutation analysis and collision multiplicity bounds with KL divergence, whereas for EWCDMD we use Hellinger distance and Fourier analysis.