The compressed permutation oracle framework, introduced to study how quantum adversaries interact with random permutations, has become an important tool for analyzing quantum security of cryptographic constructions that older techniques could not handle. A significant limitation has hampered its use, however: the method's soundness — the guarantee that the compressed representation faithfully captures the oracle's behavior — was previously established only up to O(N^{1/12}) queries to a permutation on N elements, a bound researchers have considered far too conservative to be useful in practice.
This unreviewed preprint, not yet peer-reviewed, claims to close most of that gap, raising the soundness bound to Ω(N^{1/2}) and arguing this is essentially tight. The authors also report a conceptual simplification of the underlying proof, constructing the central compression isometry via a straightforward POVM applied to a naive purification of the oracle state rather than the more elaborate machinery used previously. They extend the result to the ideal cipher model, covering the same bound in that setting without additional overhead.
The authors identify concrete immediate consequences: their improved theorem yields tight quantum collision and pre-image resistance lower bounds for the sponge construction underlying SHA3 and the Davies–Meyer compression function used in SHA1 and SHA2. More broadly, they position the result as a general-purpose tool for quantum security proofs wherever random permutations or ideal ciphers appear as primitives. As with all preprints, these claims await independent scrutiny and formal peer review before they can be considered established results.