Can the compressed-oracle technique be extended to permutations?
The oracle has been defined; proving it sound is the open half
Motivation
Zhandry’s compressed oracle changed what is provable in the quantum random oracle model. Rather than fixing a random function in advance, the oracle carries a superposition of partial function tables as its internal state — and because a proof may inspect that state, arguments that are routine classically become available quantumly.
Nothing equivalent exists for permutations. That matters because symmetric cryptography largely lives in the ideal-permutation setting: block ciphers, sponge constructions, and anything analysed with forward and inverse access to an idealised permutation. Unruh’s paper calls it “a long-standing open question … whether a similar technique can also be used to reason about random (efficiently invertible) permutations.”
Provenance and history
From Unruh, Towards compressed permutation oracles, ePrint 2023/770, ASIACRYPT 2023, pp. 369–400. Single ePrint posting, received 26 May 2023, byte-identical to the copy harvested here.
The title is doing real work. The paper defines a compressed permutation oracle (CPO) that keeps a superposition of partial functions and answers forward and backward queries, and it is candid about the split: “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.
What is settled and what is not
| status | |
|---|---|
| defining a compressed permutation oracle | done — this is the paper’s contribution |
| CPO is indistinguishable from a random permutation with inverse access — the paper’s Conjecture 2 | open — tracked as c/0036 |
| double-sided zero search is hard — the paper’s Conjecture 1 | open — tracked as c/0037 |
| if some permutation-construction is indistinguishable from CPO, then CPO is indistinguishable from a random permutation | proved — the paper’s Theorem 1, with a computational variant in Corollary 1 |
| Conjecture 2 \(\Rightarrow\) Conjecture 1 | proved — the paper’s usage example, p. 13 |
The last line is the shape of the paper: a tool whose soundness is conjectured, and an application derived from it. Neither endpoint is established, and the dependency runs one way only — the source does not claim the converse, so c/0037 could in principle fall to a technique that never mentions CPO.
The third line is the paper’s actual result, and it relocates the difficulty rather than removing it. Discharging its hypothesis would settle c/0036 through the converse the paper already has — which is probably the most concrete route in.
The problem the tool exists for
c/0037 is worth reading first, because it shows how bare the ground is. Take a random permutation on \(\{0,1\}^{2n}\), give the adversary quantum access to it and its inverse, and ask for one input whose low half is zero mapping to an output whose low half is zero. Classically that is a routine calculation. Quantumly the source reports that no hardness result is known at all — “not even simple query complexity results such as the hardness” of this.
The reason the obvious shortcut fails is instructive: a random permutation is quantumly indistinguishable from a random function, and compressed-oracle machinery handles random functions — but only with forward access. Hand over the inverse and the substitution collapses, because a random function has no inverse to hand over.
Why permutations resist the technique
For a random function the compressed oracle works because each query can be answered by a local update to the internal state. A permutation must remain injective, and an inverse query reads the same table from the other side, so the two directions constrain each other globally rather than locally. That is the structural reason the function argument does not transfer, and it is why the easy half of this problem is the definition.
A note on this site’s taxonomy
The object here is a random invertible permutation accessed quantumly, and the model vocabulary has no slug for it: icm names the right object with classical connotations, qrom the right access with the wrong object. c/0036 is filed as other rather than forced into either. If more of this literature is harvested, a quantum-ideal-permutation slug would be worth adding.