Compressed Permutation Oracles Revisited

What it is

"Compressed Permutation Oracles Revisited" (Carolan, U. Maryland; Majenz, TU Denmark; arXiv:2609.28469v1, 23 Sep 2026) reworks the soundness proof of the compressed permutation oracle. The summary states the headline (O(N^1/12) → tight Ω(N^1/2) via a POVM construction); what follows are the concrete numbers the summary omits.

The bounds it actually establishes

The distinguishing advantage between the compressed oracle and a uniform random permutation on N elements, for an algorithm making q forward/inverse queries, is:

O(q/√N) — so the simulation is sound whenever q = o(√N).

The same bound holds in the ideal cipher model independently of the number of keys, including queries in superposition over keys (each key gets an independent compression map; a query touches only the selected key's permutation). The theorem carries explicit constants, which is what makes the downstream bounds concrete rather than asymptotic.

Concrete application bounds (T = queries to obtain and verify output transcripts):

• Sponge, digest length d, capacity c:
• preimage: O(T²/2^d + T³/2^c)
• collision: O(T³/2^d + T³/2^c)
• specialized to all four SHA-3 parameter sets in the random permutation model.
• Davies–Meyer, n-bit blocks (covers SHA1/SHA2 compression):
• preimage: O(T²/2^n)
• collision: O(T³/2^n)
• holds in the ideal cipher model too.

How the proof works

The compression isometry Ṽ is built directly from the naive purification. Each size-r partial permutation f maps to a completion state |T_f⟩ (uniform superposition over permutations extending f); these overlap, so the raw map isn't norm-preserving. The states are split into orthogonal "levels" H_r (directions first appearing at size r), and the level-r frame is normalized by the inverse square root of its Gram matrix G_r = Γ_rΓ_r†. Representation theory of S_N makes G_r act as a scalar on each irrep, giving the explicit sandwich:

I ⪯ G_r ⪯ exp(r/(N−2r+1))·I, for r ≤ (N−1)/2.

Equivalently, compression is the coherent implementation of the pretty-good measurement on the completion states — which is optimal for minimum-error discrimination here because the states form an orbit under a transitive group action. The per-query error is O(1/√(N−t)) on the first t+1 levels; after t queries the register sits on levels ≤ t, and errors add to O(q/√N + q²/N) = O(q/√N).

Why it matters

The improvement is not incremental packaging. Under the old O(N^1/12) soundness, the simulation error could dominate a security bound even when the database analysis gave the expected result — meaning the tool couldn't certify the bounds you'd expect for SHA-3/SHA-2-scale parameters. At q = o(√N) with explicit constants, the technique now yields the concrete, usable quantum lower bounds above. If you were relying on prior compressed-permutation-oracle results (from [Car25]) for a quantum security argument over random permutations or ideal ciphers, this supersedes the soundness step and tightens whatever bound depended on it.

Caveats

Sponge bounds are stated in the random permutation model (Davies–Meyer results extend to the ideal cipher model). The G_r bound holds only for r ≤ (N−1)/2. This is a proof-technique paper — the deliverable is stronger provable bounds and a reusable tool, not an implementation change.