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 conditional converse on p. 14. Sole authorship, venue and page range confirmed against DBLP, which records the published title with initial capitals.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open, and the source’s title — Towards compressed permutation oracles — is accurate about how far it gets.
What the paper actually proves. Its Theorem 1 is a conditional converse: if some permutation-construction is indistinguishable from CPO, then CPO is indistinguishable from a random permutation. Corollary 1 gives a computational variant of the same conditional statement. So the paper reduces the conjecture to a different indistinguishability claim rather than establishing it — and the paper is explicit that nothing about the conjecture itself is settled in it.
Why the inverse query is the difficulty. For functions, the compressed oracle works because the internal state can be updated locally on each query. A permutation must stay injective, and an inverse query interrogates the same table from the other side, so the two directions constrain each other globally. That is the structural reason the function technique does not simply carry over, and it is why the definition is easy while the soundness is not.
What a proof would unlock. The compressed-oracle technique is how most quantum random-oracle proofs are done. An analogue for permutations would open the same style of argument for constructions built on ideal permutations — the setting most symmetric cryptography actually lives in.
Two things are worth keeping apart on this page. Defining CPO is a contribution and it exists; the soundness statement is a conjecture and it does not. A reader skimming the source’s abstract could easily take the first for the second, which is precisely why the paper’s title begins with Towards.
There is also a modelling point worth recording. 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. The ideal-cipher slug icm names the right object but carries classical connotations; qrom names the right access but the wrong object. This entry is filed as other rather than forcing a fit, and the gap is a small argument for adding a quantum-ideal-permutation slug if more of this literature arrives.