Hardness of Double-Sided Zero Search

•

Statement: AI-written, not yet formalized. Proof: human draft, not yet independently reviewed, not yet formalized.

Compressed OracleQuantum Query Complexity

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.
  • Carolan. Compressed Permutation Oracles. Cryptology ePrint Archive, Report 2025/1734; accepted to STOC 2026 (also arXiv:2509.18586). Read at the ePrint PDF. The problem, named as “the double-sided zero search problem, due to Unruh [Unr21; Unr23],” is Problem 3, p. 72; the general predicate-search bound it specialises is Theorem 7.5, pp. 70–72; the specialisation is Corollary 7.6, p. 72.

Resolved, unconditionally, by a paper this page’s Statement was not transcribed from. Carolan (Compressed Permutation Oracles, ePrint 2025/1734, accepted STOC 2026) proves this conjecture outright, and does so without depending on the still-unsettled question at c/0036.

The exact match, checked against the PDF. Carolan’s Problem 3 (p. 72) reads: “Sample \(\varphi \sim \mathbf{S}_N\) for \(N = 2^{2n}\)… \(\mathcal{A}\) makes \(q\) queries to \(\mathcal{O}_\varphi\), and succeeds if it finds \((x\|0^n, y\|0^n)\) such that \(\varphi(x\|0^n) = y\|0^n\)” — word for word this page’s conjecture, on the same domain \(\{0,1\}^{2n}\) with the same low-half-zero condition on both sides. Carolan’s own text names it: “the double-sided zero search problem, due to Unruh [Unr21; Unr23].” His Corollary 7.6 bounds the winning probability of any \(q\)-query algorithm by \(O(q^2/2^n + \mathrm{Dist}(q)^2)\), where \(\mathrm{Dist}(q) = O(q^3/N^{1/4})\) is the (already negligible, for polynomial \(q\)) distinguishing advantage against his compressed permutation oracle from his Theorem 5.19 — giving an overall bound negligible in \(n\) for every polynomial query count, exactly this page’s conclusion.

Why this does not route through c/0036. Unruh’s own paper derives this conjecture from CPO soundness (his Conjecture 2) as a usage example, and says so explicitly: “the validity of this example rests on Conjecture” 2. Carolan’s derivation has a different shape. It goes through his own Theorem 7.5 — a general predicate-search lower bound proved directly from his compressed permutation oracle’s soundness (his Theorem 5.19, an unconditional, proved result about his own construction, not Unruh’s) — and Corollary 7.6 specialises that general bound to this predicate. Since Theorem 5.19 is proved outright for Carolan’s construction, this page’s statement is now settled independent of whatever residual gap remains around Unruh’s specific Conjecture 2 — see c/0036 for why that gap is judged to remain open rather than closed by the same paper.

What has and hasn’t been checked here. Confirmed directly from the PDF: the abstract’s claim to “re-prove… hardness of double-sided zero search,” Problem 3’s statement (p. 72), Theorem 7.5’s general bound (pp. 70–72), and Corollary 7.6 (p. 72). Not independently re-derived here: the proof of Theorem 7.5 itself, which rests on the cromulence/twirling machinery built in Sections 4–6, or the proof of Theorem 5.19. This is a human-written, published (STOC 2026-accepted) proof, matched against this page’s formalisation by AI review rather than an independent human cryptographer or a machine-checked formalization — see Open obligations.

This entry, c/0036, and c/0038 all trace to one 22-page Unruh note, and for a long time sat as one conjectural tool (c/0036) and two applications of it (c/0037, this page, and c/0038). That structure is now out of date for this page: Carolan’s 2025 paper proves this statement directly from his own compressed permutation oracle, which he proves sound outright rather than conjecturing — so the dependency on c/0036 that Unruh’s own paper built in no longer describes how the statement is established.

It is worth registering how striking the prior state of the art was. 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, Unruh’s 2023 paper reported that not even this was provable. Carolan’s 2025 paper closes exactly this gap, and the fact that it does so with a proof that does not route through Unruh’s specific CPO-soundness conjecture is precisely the “more valuable” outcome this page’s Discussion previously flagged as worth hoping for, before Carolan’s paper was known to exist.

Resolved by a 2025 follow-up, independent of c/0036’s residual gap

Joseph Carolan’s Compressed Permutation Oracles (Cryptology ePrint Archive 2025/1734, accepted STOC 2026, also arXiv:2509.18586) engages Unruh’s paper directly, citing it as [Unr23] throughout, and its abstract states it will “re-prove essentially all known quantum query lower bounds in the random permutation model, notably… hardness of double-sided zero search.” The mechanism is a new compressed permutation oracle construction (Section 3), proved unconditionally sound (Theorem 5.19), from which a general predicate-search lower bound (Theorem 7.5) is derived and then specialised to this problem (Corollary 7.6). See c/0036 for the reasoning on why this new construction is judged not to unconditionally settle Unruh’s own CPO-soundness conjecture, even though it fully settles this page.

  • No independent human or machine-checked review of Carolan’s proof yet. This page’s Proof tab confirms Carolan’s Problem 3, Theorem 7.5, and Corollary 7.6 match this page’s statement, checked directly against the paper’s PDF. It does not independently re-derive Theorem 7.5’s proof or the cromulence/twirling machinery of Sections 4–6, or re-check the sparsity calculation \(s_t(\mathcal{R}) = O(2^n)\) used in Corollary 7.6. proof_review is graded ai for exactly this reason.
  • Not yet formalized. Neither this page’s statement nor Carolan’s proof has a Lean formalization; statement_formal, statement_match, and proof_formal all remain open.
  • Whether the \(\{0,1\}^{2n}\) block structure and the zero-half condition are essential, or whether the hardness is an instance of a more general statement about structured preimages — Carolan’s Theorem 7.5 suggests the latter (it bounds any predicate by its “sparsity”), and this page’s specific instance is now just one corollary among several (sponge, Davies–Meyer, cycle-finding, one-more) that Theorem 7.5 also covers, worth cross-checking against those.
  • Whether Carolan’s bound is tight. The paper’s own Discussion after Corollary 7.6 notes prior work already gives tight bounds for this problem, and that Carolan’s bound “would be tight, ignoring the \(\mathrm{Dist}(q)^2\) term” — a reviewer should check this comparison rather than take it on the paper’s word.