Paper 2026/314

Structural Tightness of Quadratic Multi-Query Bounds for Universal Hashing: Applications to Accordion Modes

Abstract

Universal hashing gives a pairwise guarantee: for two distinct messages, the probability of any fixed keyed-hash output difference is at most $\varepsilon$. Summing over the $\binom q2$ query pairs gives the familiar multi-query upper bound $\binom q2\varepsilon$, but this union bound does not show that one transcript can realize quadratically many useful pairwise events. We study when a single algebraically structured query set can do so by arranging many substantially different key conditions whose solution sets spread across the key space. Catching gives a simple chosen-offset baseline, while action-invariant grouping provides both a general analysis tool and an attack-search methodology based on message transformations, key relabelings, relative actions, and solution-set overlap. For POLYVAL, and for $\operatorname{NH}[w]$ when even $w\geq4$, we obtain zero-offset constructions in which every query uses output offset zero and balanced partial sets already achieve $\Theta(q^2\varepsilon)$ growth up to absolute constant factors. Thus the quadratic phenomenon can be intrinsic to keyed-hash algebra rather than caused by chosen output offsets. We then show that the same key-space coverage principle survives inside complete accordion modes. HCTR2 gives expected-list recovery of its derived POLYVAL subkey: the true subkey is always included and the candidate list has expected size $2$ in the ideal-permutation model. In ddd-AES the consequence is stronger than distinguishability: with $2^{65}$ fixed-tweak chosen plaintexts of length $384$ bits, exactly one observable cross-pair is the internal POLYVAL catch and it deterministically determines the full $128$-bit POLYVAL key $L$.

Note: Major revision following an early rejection at Asiacrypt 2026.