Soundness of the Compressed Permutation Oracle

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

View PDF · LaTeX source · Formal statement — not yet formalized

Zhandry’s compressed-oracle technique made quantum random functions tractable: instead of a random function fixed in advance, the oracle keeps a superposition of partial function tables as its internal state, and a proof may inspect that state. The technique underpins much of what is provable in the quantum random oracle model.

The corresponding question for permutations is, in the source’s words, “a long-standing open question … whether a similar technique can also be used to reason about random (efficiently invertible) permutations.”

The source defines the object. A compressed permutation oracle (CPO) keeps a superposition of partial functions as its internal state and answers both forward and backward queries. Its own assessment of the two halves of the problem: “It turns out that defining such a CPO is not too hard. What is hard (and what we will only make a step towards in this paper) is to prove that the CPO is indeed” sound.

Conjecture (soundness of CPO). For every polynomial $p$ there is a negligible $\mu$ such that for every finite set $D$ with the group operation used in the construction, every flipping operator $\mathsf{Flip}$, and every oracle algorithm $A$ making at most $p(\log|D|)$ queries,

\[\Bigl|\ \Pr\bigl[A^{\mathsf{CPO}} \Rightarrow 1\bigr] \;-\; \Pr\bigl[A^{U_\pi,\,U_{\pi^{-1}}} \Rightarrow 1 \;:\; \pi \xleftarrow{\$} \mathrm{Perm}(D)\bigr]\ \Bigr| \;\le\; \mu .\]

That is: no bounded-query algorithm with forward and inverse access can tell the compressed permutation oracle from a genuinely random permutation.

Sources

Unruh. Towards compressed permutation oracles. Cryptology ePrint Archive, Report 2023/770; Advances in Cryptology – ASIACRYPT 2023, pp. 369–400. Read at the single ePrint posting, received 26 May 2023, byte-identical to the harvested copy (SHA-256 prefix e32e1eb4a186bb37, 22 pages), whose title page is dated 26 May 2023. The long-standing-open-question framing is on p. 1; the second use case and what remains unknown about it on p. 3; the CPO definition and the easy-versus-hard remark on p. 12; the flipping-operator definition and its underspecification on non-injective inputs on p. 12 (footnote 20 explicitly: “we make sure that our results hold independent of the design choices for that case”); the conditional converse on p. 14. Sole authorship, venue and page range confirmed against DBLP, which records the published title with initial capitals.
Carolan. Compressed Permutation Oracles. Cryptology ePrint Archive, Report 2025/1734; accepted to STOC 2026 (also arXiv:2509.18586). Read at the ePrint PDF. The footnote stating Unruh’s soundness “is only conjectured” is p. 5; the “small modification… explicitly and unitarily maintain injectivity” remark is p. 17; the compression operator’s exact definition (restricted to non-colliding outputs) is Equations 56–58, p. 18; the flip operator’s definition is Equation 60, p. 18; the formal soundness theorem is Theorem 5.19, p. 57.

Not resolved as formalized on this page, though a closely related and unconditional result now exists. This is the most consequential judgment call on this page, so the reasoning is spelled out in full rather than asserted.

What Carolan actually proves. Compressed Permutation Oracles (Carolan, ePrint 2025/1734, accepted STOC 2026) builds a compressed permutation oracle, cpO, and proves (his Theorem 5.19, p. 57): “Any $q$ query quantum algorithm cannot distinguish the compressed permutation oracle from a uniform random permutation oracle on $[N]$… except with advantage $O(q^3/N^{1/4})$. In particular, constant advantage requires $\Omega(\sqrt[12]{N})$ queries.” This is an unconditional theorem, not a conjecture — confirmed directly against the PDF, not taken from the abstract.

Whether cpO is “the CPO” this page’s Conjecture quantifies over. The Conjecture above is universally quantified over “every flipping operator $\mathsf{Flip}$” — but that quantifier ranges over the free choice left in Unruh’s own Definition 1, holding fixed everything else about how the compression operator works. Unruh’s construction answers forward queries with CFOs, the plain compressed function oracle (Section 3 of his paper) reused verbatim for a permutation’s domain and range: on a fresh input, CFOs decompresses to a uniform superposition over all of $D$ (via the Fourier-derived $|\ast\rangle$ state) and compresses back, with no mechanism preventing the newly sampled output from colliding with one already in the database. This is why Unruh’s database can, with small but non-zero amplitude, land on a non-injective partial function after some queries — and why Flip needs a specified (if inconsequential, per Unruh’s own argument) behaviour there at all: Flip|h\rangle = |h^{-1}\rangle is forced only for injective $h$, and the paper explicitly leaves the non-injective case a free choice, subject only to $\|\mathsf{Flip}\| \le 1$ (p. 12, footnote 20).

Carolan’s cpO does not merely pin down that free choice. Its compression operator, $\mathsf{pC}$ (his Equations 56–58), is a different unitary: on a fresh input $x$ against database $I$, it swaps the undefined placeholder specifically with the uniform superposition over outputs not already in $\mathrm{Im}(I)$ — i.e., collisions are excluded from the superposition by construction, not merely made negligible by chance. Carolan states this in his own words: “Our construction is similar to that of Unruh [Unr23], though we explicitly and unitarily maintain injectivity of the database” (p. 17) — and separately, in his introduction’s technical summary: “the compression operator explicitly maintains injectivity of the database” (p. 4). As a direct consequence, the purifying register in cpO is, exactly (not approximately), “spanned by all injective partial functions” (p. 57) at every step. cpO’s flip operator $\mathsf{F}$ is defined identically to Unruh’s Flip on the only case that matters — $\mathsf{F}|I\rangle = |I^{-1}\rangle$ for injective (partial) $I$ (his Equation 60) — but because $\mathsf{pC}$ never produces a non-injective $I$, $\mathsf{F}$ never needs a definition beyond that case. The free choice this page’s Conjecture universally quantifies over literally never arises in Carolan’s construction.

The judgment call. Is a compression operator that excludes colliding outputs from its superposition, rather than tolerating them with vanishing amplitude, “just” an instantiation of the free choice Unruh’s own Theorem-1 proof shows soundness is invariant to — or is it a structurally different oracle? Weighing this directly: Unruh’s own invariance argument (the sanitization-by-projector technique in his Lemma 1’s proof, p. 16–17) is about how Flip acts on the negligible-amplitude non-injective states his CFOs-based construction actually visits — it says nothing about, and gives no technique for, comparing a construction that never visits those states at all, built from a different compression rule. The two oracles agree on injective inputs and on the intent (compress a permutation’s truth table, answer both directions); they disagree on the actual unitary applied to extend the database on each forward query, which is exactly the operator Unruh’s own soundness question is about. No lemma in either paper compares cpO to Unruh’s CFOs-based CPO directly (both are compared only to the true random-permutation oracle, not to each other). Concluding from this that Carolan’s Theorem 5.19 settles this page’s Conjecture would require an unwritten bridging step — showing cpO and Unruh’s CPO are themselves indistinguishable, for every valid choice of Flip — and that step is not obviously routine: it is a comparison between two constructions with different compression mechanics, not a comparison between two choices of a free parameter within one fixed mechanism. The verdict adopted here is therefore: a genuine, specific residual gap, not a closed conjecture. What is closed is the broader, informally-stated research question this page’s Statement opens with — “whether a similar technique can also be used to reason about random (efficiently invertible) permutations” — which Carolan answers yes to, via a construction of his own.

A sanity check against overclaiming the gap. It is plausible, and arguably likely, that a hybrid/triangle-inequality argument bridging cpO and Unruh’s CPO could be written without great difficulty, in the same way Unruh’s own paper shows his sanitized and non-sanitized compressed function oracles (CFOs and CFO) are “perfectly indistinguishable” (p. 9–10) despite being syntactically different unitaries. But “plausible and probably not hard” is not the same as “proved,” and no paper read for this page carries out that argument. This page therefore stays open rather than solved, with the gap named precisely rather than left as a vague caveat — see Open obligations.

Why the flip-operator quantifier exists in the first place, and what it was really formalizing. Reading Unruh’s own text closely (p. 12) clarifies that “for every flipping operator $\mathsf{Flip}$” in this page’s Conjecture was never meant to range over fundamentally different strategies for inverting a permutation — $\mathsf{Flip}|h\rangle = |h^{-1}\rangle$ is forced, uniquely, on every injective $h$, which is the only case a well-formed permutation’s database should ever actually be in. The quantifier exists only because Unruh’s own construction can (with small amplitude) leave that “should never happen” case, and his own footnote 20 says outright that the paper’s results are designed to “hold independent of the design choices for that case.” So the quantifier in this page’s formalized Conjecture is doing exactly what it looks like it is doing: formalizing invariance to a junk-input convention, not asking for a proof that works across meaningfully different oracle designs. That is a faithful reading of Unruh’s intent.

Why Carolan’s fix is not, on inspection, only a junk-input fix. The natural first guess — that Carolan simply picked a canonical answer for Flip on non-injective inputs and thereby instantiated Unruh’s conjecture for that choice — turns out not to fit the construction once the compression operator itself is read. Carolan’s $\mathsf{pC}$ changes which outputs are ever eligible to be sampled on a fresh query (excluding used ones, rather than sampling uniformly over everything and accepting the small collision risk); this is a change to the forward-query mechanism, upstream of where Flip ever enters, and it is what makes the injective-only invariant exact rather than approximate. Unruh’s own construction could not have this property without an analogous redesign of CFOs itself — which is precisely what Carolan built, and precisely why Carolan and not Unruh required “much more difficult” (Carolan’s own words, p. 17) work to prove soundness, despite the two constructions looking similar at a glance.

Why this still counts as resolving the research question, just not this exact formalization. The long-standing question this page’s Statement opens with is whether the compressed-oracle technique — lazy sampling that survives superposition queries — extends from functions to invertible permutations at all. Carolan answers that unambiguously: yes, with an explicit query bound. A reader mainly interested in “is there a sound compressed permutation oracle” should treat this page as settled in spirit. A reader who needs precisely Unruh’s Conjecture 2, construction and all — for instance, to cite it as already proved in a context that specifically depends on Unruh’s CFOs-based definition — should not, on the reasoning here, treat it as such without independently checking the bridging argument sketched above.

Modelling point, unchanged. The object being idealised here is a random invertible permutation accessed quantumly, and this site’s taxonomy has no slug for that — MODELS offers rom, prom, icm, ggm, qrom, standard, other. This entry is filed as other rather than forcing a fit; Carolan’s paper does not change this modelling gap, since it doesn’t touch this site’s taxonomy either.

The residual gap, precisely stated. Prove or disprove: Unruh’s CPO (Definition 1 of his paper: forward queries via CFOs, backward via $\mathsf{Flip}\cdot\mathsf{CFOs}\cdot\mathsf{Flip}$, for any $\mathsf{Flip}$ satisfying his constraints) is negligibly close, for every polynomial-query algorithm, to Carolan’s cpO. If this bridging lemma holds, it combines with Carolan’s Theorem 5.19 by the triangle inequality to prove this page’s Conjecture in full, closing this page as research-solved. If it fails, the failure would itself be informative about exactly how much the “explicitly and unitarily maintain injectivity” design choice buys beyond junk-input invariance.
Independent review of the reasoning above. The judgment that Carolan’s compression-operator redesign is a substantive change (not just an instantiation of the free Flip choice) is this page’s own analysis, checked against both papers’ PDF text but not against any third-party reading. A human cryptographer familiar with compressed-oracle proofs should sanity-check it before this page is treated as settling anything beyond what is stated here.
No independent human or machine-checked review of Carolan’s Theorem 5.19 itself. Confirmed directly from the PDF: the theorem statement, the compression operator’s definition, and the flip operator’s definition. Not independently re-derived: the soundness proof (Sections 4–5 of Carolan’s paper), which is long and technical.
Not yet formalized. Neither this page’s statement nor either paper’s proof has a Lean formalization; statement_formal, statement_match, and proof_formal all remain open.
Determine whether the negligible bound in this page’s Conjecture can be made concrete. Carolan’s Theorem 5.19 gives an explicit polynomial bound ($O(q^3/N^{1/4})$) for his own construction; whether the same concrete rate applies to Unruh’s original construction (contingent on the bridging lemma above) is unresolved.
Establish whether Unruh’s original CPO is sound for some choices of the free non-injective behaviour but not others. Unruh’s own paper argues invariance across that choice, but this page has not independently re-verified that argument; it is listed here rather than assumed.