eprint.iacr.orgpaper

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

Proves that the nonce-based MACs Encrypted Wegman-Carter (EWC) and EWCDMD (the dual of EWCDM) are unforgeable beyond the birthday bound. With an n-bit block cipher and an O(2^-n)-AXU hash, both are secure up to 2^{5n/6} MAC queries and nearly 2^n verification queries in the nonce-respecting setting. This settles an open question left by earlier birthday distinguishing attacks (Cogliati–Seurin on EWC, Nandi on EWCDMD), which never yielded forgeries. The proofs analyze forgery events directly through auxiliary experiments. The EWC proof adds conditional permutation analysis and collision multiplicity bounds with KL divergence, and the EWCDMD proof uses Hellinger distance and Fourier analysis.