Hardness of Double-Sided Zero Search

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

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

Let $H$ be a uniformly random permutation on $\{0,1\}^{2n}$, and give the adversary quantum access to both $H$ and $H^{-1}$. Ask it to find an input whose low half is zero and whose image also has low half zero.

Conjecture (hardness of double-sided zero search). For every polynomial $p$ there is a negligible $\mu$ such that for all $n$ and every oracle algorithm $A$ making at most $p(n)$ queries,

\[\Pr\Bigl[\ \exists\, y \in \{0,1\}^{n} : H(x \| 0^{n}) = y \| 0^{n} \ \Bigm|\ H \xleftarrow{\$} \mathrm{Perm}(\{0,1\}^{2n}),\ x \leftarrow A^{U_H, U_{H^{-1}}}()\ \Bigr] \;\le\; \mu(n).\]

This is about as simple as a query-complexity question about permutations gets — which is the point of it.

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). The conjecture is stated on p. 12, together with the remark that existing techniques do not reach superposition access to random permutations and the random-function substitution that fails; the absence of any hardness result for invertible random permutations is on p. 2; the conditional derivation from CPO is on p. 13. Sole authorship, venue and page range confirmed against DBLP.

View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized

Open, and the reason it is open is worth quoting rather than paraphrasing: “no hardness results are known about invertible random permutations, not even simple query complexity results such as the hardness” of this problem.

What the source does. It proves the conjecture under its own compressed-permutation-oracle soundness conjecture — see c/0036 — presenting it as the usage example for that tool: “We now illustrate how the CPO can be used by showing Conjecture 1 (double-sided zero-search) using the CPO. Of course, the validity of this example rests on Conjecture” 2. So this page’s statement is a corollary of a conjecture, not of a theorem.

Why the obvious route is blocked. A random permutation is indistinguishable from a random function in the quantum setting, and for random functions the compressed-oracle technique applies. But that indistinguishability is for forward access only: hand the adversary $H^{-1}$ as well and the substitution fails, because a random function has no inverse to give. The source makes exactly this point, and it is why “even simple questions relating to (superposition access to) random permutations are to the best of our knowledge not in the scope of existing” techniques.

So the missing thing is a toolkit, not a calculation. That is the honest reading of why a problem this easy to state has no proof, and it is why the same paper spends its length building the CPO rather than attacking this directly.

This entry and c/0036 are the two halves of one paper and are best read together: c/0036 is the tool, this is the motivating application, and the paper’s contribution is the conditional link between them. The dependency runs one way — CPO soundness gives double-sided zero search, and the converse is not claimed.

It is worth registering how striking the state of the art is. The problem asks for a single input satisfying a $2n$-bit condition under a random permutation, with polynomially many queries. Classically it is a routine birthday-style calculation. Quantumly, with inverse access, the source reports that not even this is provable — and that gap is a fair summary of why quantum-query analysis of block-cipher-style idealisations lags behind the random-oracle case.

A note for anyone attacking it: a proof that does not route through CPO would be more valuable than one that does, since it would settle this without waiting on c/0036. Nothing in the source suggests such a route exists, but nothing rules it out either — the paper’s framing is that no technique reaches this setting, not that this problem is equivalent to CPO soundness.

Prove the hardness bound unconditionally, or exhibit a polynomial-query quantum algorithm that finds such an $x$.
Prove c/0036, which yields this statement through the source’s own argument.
Determine whether double-sided zero search is equivalent to CPO soundness or strictly weaker — the source claims only one direction.
Establish any hardness result at all for invertible random permutations under quantum access, which the source says is currently absent.
Work out whether the $\{0,1\}^{2n}$ block structure and the zero-half condition are essential, or whether the hardness is a general statement about structured preimages.
Formalize the statement in Lean; quantum oracle access with an inverse oracle needs writing down first.