PaperlayerView exact revision on arXiv

Source-linked AI summary

EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity

Atul Mantri

arXiv:2609.11901v1quant-phcs.CR

TL;DR

The paper asks whether EFI pairs can exist without the classical average-case hardness embodied by one-way puzzles. It constructs a classical oracle that removes one-way puzzles while preserving a half-subspace EFI pair under coherent-last access, using communication complexity and random-matrix bounds. Relative to this oracle, quantum polynomial time offers no advantage on classical-input, classical-output tasks, although broader coherent-access security remains open.

  • Problem

    Whether EFI pairs imply one-way puzzles is open, leaving unresolved whether quantum cryptography’s minimal assumption can be separated from classical average-case hardness.

  • Method

    The authors construct a classical oracle that answers exact output-probability queries and hides a Haar-random half-dimensional subspace, proving security through communication complexity and random-matrix tools.

  • Results

    The oracle has no one-way puzzles even with an unbounded verifier, while its efficiently generatable half-subspace pair remains indistinguishable against coherent-last distinguishers.

  • Takeaways & Limitations

    Relative to the oracle, quantum polynomial time gains no advantage on tasks with classical inputs and outputs, while hardness survives as indistinguishability between two quantum states.

  • Takeaways & Limitations

    The EFI security result restricts superposition access to one final coherent query and does not cover coherent queries placed earlier or multiple coherent queries.

Abstract

from arXiv · show

EFI pairs (Brakerski, Canetti, and Qian, ITCS 2023) and one-way puzzles (Khurana and Tomer, STOC 2024) are the leading candidates for the minimal assumption of quantum cryptography. The first are efficiently preparable quantum states, statistically far yet computationally indistinguishable; the second are classical puzzles, easy to sample and hard to solve. One-way puzzles imply EFI pairs, and whether the converse holds is open. We construct a single classical oracle relative to which one-way puzzles do not exist, even with an unbounded verifier, while an EFI pair survives every distinguisher that queries the oracle classically throughout and holds advice about it, making its one superposition query at the end. The oracle answers every question about the output probabilities of quantum samplers, which removes the puzzles, and hides a Haar-random half-dimensional subspace. To prove security we reduce it to communication complexity. An adversary whose knowledge of the subspace arrives as classical query answers can be simulated inside a two-party protocol against the party holding it, so it does no better than the best classical protocol for Vector-in-Subspace (Klartag and Regev, STOC 2011), whatever the oracle computes. That argument does not cover the superposition query, which we bound instead using tools from random matrix theory. The same attack gives a classical simulation of any quantum party in a classical-message protocol with no entanglement shared in advance, so relative to the oracle there is no proof of quantumness either. Quantum polynomial time therefore offers no advantage on any task with classical inputs and outputs, while the two quantum states stay indistinguishable. We state conjectures on removing the restriction on superposition queries.

1 Introduction

The paper separates EFI pairs from one-way puzzles using a single classical oracle: puzzles disappear, while a half-subspace EFI pair remains secure against coherent-last distinguishers. Its proof combines classical communication lower bounds with random-matrix arguments, and also eliminates quantum advantages in classical-message protocols.

  • 1 Introduction: One-way puzzles imply EFI pairs, but whether EFI pairs imply one-way puzzles remains open.The question asks whether quantum indistinguishability necessarily entails classical average-case search hardness.
  • 1.1 Main results: The oracle uses exact output-probability answers to make quantum-sampler estimation easy, while hiding a Haar-random half-dimensional subspace.A rank condition prevents circularity by restricting each counting query to lower-rank samplers.
  • 1.1 Main results: A deterministic classical oracle eliminates one-way puzzles even for unbounded verifiers while preserving an EFI pair against coherent-last distinguishers.The pair is efficiently generatable, has TD ≥1 −2−Ω(λ), and every allowed distinguisher has advantage 2−Ω(λ).
  • 1.1 Main results: The result applies to classical queries without access restrictions, but EFI security permits only one final coherent query and bounded quantum advice.Removing the coherent-last and advice restrictions simultaneously is left to conjectures.
  • 1.1 Main results: Classical query-and-answer traffic is reduced to communication with the hidden subspace, where Vector-in-Subspace hardness bounds the distinguisher’s advantage.The proof analyzes an ideal fresh-sample source before implementing it in a classical Boolean oracle.
  • 1.1 Main results: The same oracle classically simulates quantum parties in unentangled classical-message protocols, so quantum polynomial time gains no advantage on classical-input, classical-output tasks.The simulation works against counterparties with unbounded computational power, while the quantum-state indistinguishability survives.

2 Preliminaries

The preliminaries establish notation for quantum states, operators, Haar-random subspaces, oracle queries, and the distinguisher model used later. They also state the communication lower bound and characterize the security strength of the constructed EFI pair.

  • Notation: The paper fixes QPT notation, negligible functions, security parameter λ, and ambient dimension n = 2^λ.It also specifies logarithm, indicator, and total-variation conventions.
  • Notation: Trace, operator, and Hilbert–Schmidt norms, trace distance, effects, and Haar measures provide the core analytic vocabulary.Effects represent arbitrary two-outcome measurements, while Haar randomness supplies rotation-invariant random subspaces.
  • Analytic tools: Net arguments reduce Hermitian operator norms to finite maxima, while purification and Hermitian dilation support later reductions.The net has size at most 9^{2K} for a 1/4-net of a K-dimensional complex space.
  • Hidden-subspace states: The half-subspace construction uses orthogonal maximally mixed states whose trace distance is 1 and whose hidden reflection yields linear statistics.The measurement {P_H, P_H⊥} distinguishes the states perfectly when H is known.
  • Query model: The query model uses phase oracles, and arbitrary oracle-aided distinguishers are represented as channels followed by effects with advantage measured from acceptance probabilities.Phase and bit-flip access are interchangeable up to a factor-2 width change.
  • Communication background: The imported Vector-in-Subspace lower bound requires Ω(n^{1/3}) bits of classical randomized two-way communication.The preliminaries also record the small-advantage bound β(n,L) ≤ (L+1)/n^{1/3}, with β(n,0)=0.

3 Security from communication complexity

This section reduces security against adversaries whose hidden-object information arrives through classical transcripts to classical communication complexity. The resulting communication gap yields security against powerful oracle computations, while the reduction’s one-way nature and quantum-communication upper bound delimit its scope.

  • Reduction: A distinguisher receiving only classical query answers about a hidden object can be simulated as a two-party protocol with the object-holder answering queries.The reduction applies to arbitrary hidden objects and arbitrary deterministic oracles, regardless of computational efficiency.
  • Reduction: The simulation charges the classical transcript and advice, reproduces the distinguisher’s view exactly, and converts its advantage into protocol success.Advice costs at most a bits, while query traffic costs L bits plus one sign bit.
  • Limitations: Quantum communication always suffices for statistically far pairs, so this communication argument cannot address coherent queries.A logarithmic number of qubits lets the hidden-object holder perform the distinguishing measurement.
  • Security consequence: A communication gap yields average distinguishing advantage at most 2γ(L+a+1) against every deterministic oracle with L classical query bits and a advice bits.The same associated problem remains usable through a logarithmic-cost quantum protocol when the states are statistically far.
  • Security consequence: For the half-subspace pair, Vector-in-Subspace supplies the needed classical hardness, with β(n,L) bounded by the small-advantage communication estimate.The framework therefore converts classical communication hardness into security against classical-transcript adversaries.
  • Limitations: The reduction is sufficient but not necessary because Alice receives a classical challenge description unavailable to a one-copy distinguisher.Different branch descriptions can make the associated problem trivial even when the quantum pair remains hard to distinguish.

4 The oracle and the primitives it removes

The oracle makes probability estimation easy for quantum-samplable classical distributions, eliminating one-way puzzles and several primitives that imply them. At the same time, direct classical attacks exclude classical-output EFI variants and collapse quantum parties in classical-message protocols, while the paper’s EFI pair remains outside these excluded forms.

  • Probability estimation: Exponential-accuracy probability estimation uses polynomially many classical Count queries, with success probability 1.The estimate is 2^-t-additively accurate for any polynomial t.
  • One-way puzzles: Every candidate one-way puzzle, including inefficiently verifiable puzzles, is broken by a classical polynomial-time adversary using Count.The attack applies for every fixing of the hidden-subspace randomness and does not run the verifier.
  • Consequences: The oracle therefore also rules out multi-copy pseudorandom states and unitaries, pure-output one-way state generators, and pure-banknote quantum-money mini-schemes.These primitives are excluded because each implies one-way puzzles.
  • QEFID and classical-output EFI pairs: A classical polynomial-time distinguisher excludes QEFID pairs and classical-output EFI pairs, with the former’s advantage matching statistical distance up to 2^-λ.The direct argument is quantitative and works for every fixing of the hidden subspaces.
  • Interactive protocols: For quantum parties sending only classical messages, a classical Count-query simulator reproduces every interaction with any counterparty up to negligible error.The simulator samples outgoing bits from Count-accessible conditional distributions.
  • Interactive protocols: Consequently, quantum polynomial time provides no advantage for classical-output sampling and cannot yield an inefficient-verifier proof of quantumness relative to the oracle.The replacement classical prover’s acceptance probability differs by at most 2^-λ.

5 EFI security

The paper proves EFI security for a Haar-random half-subspace pair by reducing classical information about the hidden subspace to Vector-in-Subspace communication complexity, while separately controlling coherent access.

  • Reference-copy reduction: Reference copies reduce to classical spans, leaving a Haar-random Vector-in-Subspace instance in dimension n−2q and losing only a 2q/n branch.Conditioning on the spans makes the residual subspaces orthogonal complements inside the remaining space.
  • Security theorem: The resulting advantage bound remains negligible for every fixed oracle and every non-uniform adversary, even when its advice depends on the hidden subspace.The fixed-oracle argument yields negligible advantage for the entire adversary family.
  • Security theorem: The half-subspace pair is a secure EFI pair against non-uniform QPT distinguishers with polynomial reference copies, adaptive classical Count queries, one final coherent query, and arbitrary polynomial classical advice.This establishes the separation in the source model while allowing advice depending arbitrarily on the fixed oracle.
  • Optimal classical advantage: Classical attacks achieve the exact asymptotic rate 2(πn)^−1/2, so negligible security requires superpolynomial dimension n=λω(1).The construction chooses n=2^Θ(λ), giving security 2^−Θ(λ).
  • Limitations and open questions: The communication route proves O(poly(λ)·n^−1/6) security, whereas a direct linearity argument reaches poly(λ)·n^−1/2; the general two-way small-advantage question remains open.Matching the direct rate within the communication route would require a stronger estimate for two-way Vector-in-Subspace protocols.
  • One-way VSP rate: The one-way randomized communication complexity of exact Haar-distributed Vector-in-Subspace is Θ(√n), with an upper bound linear in message length at every length.The result applies to the exact promise and rotation-invariant distribution.

6 Coherent queries

The coherent-query analysis bounds how much a final superposition query or quantum advice can reveal about the hidden subspace. These bounds support indistinguishability against the paper’s restricted access model while identifying quantitative limits and separations between advice models.

  • 6.3 The one-query bound: A single coherent query has average bias bounded at the n^-1/2 scale, up to a logarithmic dependence on oracle width.The proof replaces a maximum over truth tables with an operator-norm bound whose variance is controlled by random-matrix concentration.
  • 6.3 The one-query bound: The one-query bound is nearly tight: an explicit adversary achieves bias at least (4πn)^-1/2 for oracle width M = 2^n.The gap is only a √log n factor relative to the upper bound.
  • 6.3 The one-query bound: Polynomially many parallel coherent queries remain negligible when n = 2^Ω(λ), with bias at most C√(t log(2M)/n).This result concerns parallel queries after an H-independent preparation and a single application of the oracle truth table.
  • 6.5 Classical queries followed by one coherent query: The final security theorem combines classical-query and one-coherent-query bounds, but its scope is limited to coherent-last access and does not cover unrestricted adaptive coherent queries.The construction also relates a coherent query of width M to roughly Θ(n log(2M)) qubits of advice.
  • 6.4 Quantum advice: Quantum advice of m qubits is charged at rate √m/n, remaining negligible for every m = n^{2−Ω(1)}.This bound is tight in order: Θ(n^2) advice qubits are necessary and sufficient for constant bias in the one-copy model.
  • 6.4 Quantum advice: The one-copy quantum-advice model is strictly weaker than the classical-input model, where O(n log n) classical information can yield high success while one-copy advice remains negligible.The paper therefore does not transfer the quantum-advice result to receivers that can reconstruct arbitrarily many challenge copies from a classical description.

7 The separation relative to a single classical oracle

The paper implements the separation using one deterministic Boolean oracle that both exposes sampler output probabilities and embeds a hidden-subspace state pair. Relative to this oracle, one-way puzzles disappear while the rounded half-subspace pair remains an EFI pair against coherent-last distinguishers, ruling out a corresponding black-box construction.

  • 7.1 The oracle and the generator: The oracle O′ is a single deterministic Boolean function combining a sample-encoding layer G with Count, which answers probability-estimation queries.Stored samples are rounded to a finite measurable state set before Rosenthal’s one-query synthesis is applied.
  • 7.1 The oracle and the generator: The generator G′ samples an index, performs one coherent query to G, and outputs a mixture of rounded states from the hidden subspace H or its orthogonal complement.The resulting states remain statistically far, with trace distance at least 1 − 2^{-3λ+2}.
  • 7.2 The separation theorem: Relative to O′, one-way puzzles—including inefficiently verifiable and classically secure variants—do not exist, while the generated pair is computationally indistinguishable with advantage 2^{-Ω(λ)}.The pair is efficiently generatable, statistically far, and secure against QPT distinguishers with coherent-last access.
  • 7.2 The separation theorem: Puzzle elimination uses Count to invert candidate samplers, whereas EFI security replaces stored samples by fresh ones before applying the communication reduction.Applying the reduction directly to stored samples would reveal the list from which the challenge was drawn and trivialize the associated problem.
  • 7.2 The separation theorem: The separation works because the oracle removes meta-complexity hardness while distinguishing the half-subspace pair still requires the hidden measurement {P_H, P_H⊥}.Classical query information is controlled through the Vector-in-Subspace communication gap, while the final coherent query is handled separately.
  • 7.3 The black-box barrier: There is no coherent-last fully black-box construction of one-way puzzles from EFI pairs.A successful reduction would distinguish the EFI pair after using an oracle-based inverter, contradicting the separation theorem.

8 Fully coherent access

The paper studies whether EFI-pair security survives fully coherent oracle access, conjecturing security for polynomially many adaptive queries while proving several restricted cases. Known results cover one query broadly, two queries with a narrow first query, and substantial advice regimes, but leave the general multi-query case open.

  • Model: The analysis models coherent access as ordinary quantum queries to a deterministic Boolean function of the hidden object, with query labels padded to a fixed polynomial length.The oracle’s counting layer carries sampler descriptions, outputs, and precision-bit indices.
  • Conjecture 8.2: Conjecture 8.2 asks whether EFI pairs remain secure against polynomially many adaptive coherent queries with polynomial query width, advice, and reference copies.An affirmative answer would extend the separation to the standard quantum oracle model without access-mode or advice restrictions.
  • Established cases: For one coherent query, quantum advice of m ≤ (2 − ε)λ qubits still gives average bias 2^−Ω(λ) when log M is polynomial in λ.The result permits arbitrary advice depending on the hidden subspace and one coherent query of any width.
  • Established cases: Two adaptive coherent queries remain secure when the first has width M1 ≤ n^(2−ε), regardless of the second query’s polynomial logarithmic width.This is the established two-query case with a narrow first query.

9 Discussion and open problems

The discussion interprets the security proof through communication complexity and identifies unresolved boundaries for coherent access, VSP thresholds, multiple copies, quantum advice, and oracle construction. The central remaining limitation is that classical communication reductions do not capture coherent queries, while the mixed quantum-advice-plus-classical-query case remains open.

  • Communication perspective: Classical oracle-dependent resources reduce to communication protocols for Vector-in-Subspace, whose hardness makes classical transcripts and advice largely ineffective against the hidden subspace.The oracle still leaks information, at rate Θ(n^−1/2) for measure-then-count adversaries and at most poly(λ)n^−1/6 generally.
  • Access limitations: Coherent queries lack a useful communication counterpart, so the proof handles only a polynomial classical transcript followed by one coherent query.Simulating a coherent query would require quantum communication, where Vector-in-Subspace is exponentially easy.
  • Open problems: Fully coherent security remains open because two coherent queries provide no classical record for the conditioning step used by the main proof.The unresolved case includes quantum advice together with a coherent query, beyond the regimes settled by existing propositions.
  • Open problems: The exact classical communication complexity of VSP is unknown: current bounds lie in [n^(1/3), √n], although either endpoint preserves the separation’s exponential scale.Sharper bounds would determine the exact rate at which classical counting compromises state hiding.
  • Additional questions: Other open questions concern k-VSP communication complexity, survival of mixed-banknote quantum money, and making the counting oracle uniform.Security for k challenge copies already follows from the single-copy theorem via a hybrid, but the corresponding communication problem remains open.
  • Open problems: The mixed resource of polynomial-size quantum advice plus adaptive classical Count queries remains unresolved, despite separate results for linear advice with classical queries and polynomial advice alone.The obstacle is the ordering restriction in the conditioning argument rather than a missing communication bound.

A The conditional-sampling attack

The counting oracle lets a classical polynomial-time adversary reconstruct an honest conditional key distribution from exact output-probability bits. This makes any one-way puzzle insecure, even against an unbounded verifier.

  • The conditional-sampling attack: A classical polynomial-time adversary uses exact probability bits to sample each key bit from the conditional distribution given the puzzle.It makes 2mt = poly(λ) classical queries, with t = m + ℓ + 3λ.
  • The conditional-sampling attack: The attacker’s output distribution is within 2^-λ total variation distance of the honest sampler’s distribution.The bound is TV(DA, Dreal) ≤ 4mη2^(ℓ+m) ≤ 2^-λ for sufficiently large λ.
  • The conditional-sampling attack: Hybridizing one key bit at a time proves that the approximate conditional sampler remains close to the true conditional law.Per-prefix errors are controlled using the displayed total-variation bound and a trivial TV ≤ 1 bound elsewhere.
  • The conditional-sampling attack: Because verifier acceptance is an arbitrary measurable function of the key and puzzle, the attacker succeeds without running or computing the verifier.Correctness transfers acceptance probability from the honest distribution to the attacker’s distribution.
  • The conditional-sampling attack: Thus a classical randomized polynomial-time adversary produces an accepting key with probability 1 − negl(λ), contradicting one-way-puzzle security.The argument holds for every fixing of the hidden oracle family and uses only classical queries.

B.1 The exact rate against a measure-then-count adversary

The measure-then-count analysis bounds the adversary’s distinguishing advantage using mean absolute deviations of Beta-distributed projection weights. The bound is essentially tight for computational-basis measurement, including after finite-precision truncation.

  • The exact rate against a measure-then-count adversary: For a real Haar half-dimensional subspace, each diagonal projection weight follows Beta(n/4,n/4), yielding mean absolute deviation about (πn)^−1/2.The exact-rate bounds are obtained by evaluating the symmetric Beta deviation and controlling the Gamma ratio.
  • The exact rate against a measure-then-count adversary: The complex ensemble has Beta parameter n/2, while complex vectors tested against real subspaces are handled by convexity from the real case.The convexity argument preserves the upper bound needed for the proposition.
  • The exact rate against a measure-then-count adversary: The universal upper bound on the adversary’s advantage is 2/√(πn), obtained by summing projection deviations over POVM elements.The argument permits complex POVM eigenvectors by using the complex-vector bound.
  • The exact rate against a measure-then-count adversary: Computational-basis measurement attains that upper bound within a factor 1 − O(n^−1) under the exact threshold rule.Rotation invariance and Beta symmetry reduce the expectation to the deviation of one coordinate projection.
  • The exact rate against a measure-then-count adversary: Finite t-bit truncation changes the threshold rule only when |ξj| ≤ nη, and its total loss is negligible at n = 2^λ.With η = 2^-t, the loss is dominated by the preceding O(n^-1) term.

B.2 The one-way rate: harmonic analysis on the sphere

Harmonic analysis diagonalizes the sphere operators governing the hidden-subspace leakage. At half dimension, a cancellation removes degrees ℓ ≡ 0 (mod 4), yielding the spectral structure used in the one-way-rate bound.

  • The one-way rate: harmonic analysis on the sphere: Funk–Hecke diagonalizes the rotation-invariant operators, while Chu–Vandermonde evaluates their Gegenbauer scalars.The half-dimensional setting is where the two scalar expressions can cancel.
  • The one-way rate: harmonic analysis on the sphere: At half dimension, the difference operator vanishes on harmonic degrees ℓ ≡ 0 (mod 4), because the two operator scalars cancel.The same cancellation appears directly in the product-form computation.
  • The one-way rate: harmonic analysis on the sphere: The degree-two eigenvalue is ω2 = 1/(n−1), and the remaining ω2j factors decrease with j.This degree-two value dominates the downstream estimates.
  • The one-way rate: harmonic analysis on the sphere: The second-moment operator identity follows by expanding rotation-invariant quadratic forms and applying the spectral cancellation degree by degree.The proof uses Parseval after comparing the common-subspace and opposite-subspace operators.

B.4 A level-ℓinequality, and the leakage of one cell

A level-ℓ inequality controls low-degree spherical-harmonic mass of a cell, while decay controls higher degrees. Together these bounds limit leakage from a measurable cell of the sphere.

  • B.4 A level-ℓinequality, and the leakage of one cell: The level-ℓ inequality is proved by reversing heat-semigroup damping and applying hypercontractivity at an optimized diffusion time.The choice of ε balances the hypercontractive factor against the degree-dependent semigroup prefactor.
  • B.4 A level-ℓinequality, and the leakage of one cell: For a cell A of spherical measure α, the leakage bound begins with the universal estimate E_H|μ_H(A)| ≤ 2α.Rotation invariance gives equal expected masses for H and H⊥.
  • B.4 A level-ℓinequality, and the leakage of one cell: Splitting the harmonic sum at j* = ⌈ln(e/α)⌉ lets the level-ℓ inequality control low degrees and ω-decay control high degrees.The two ranges use different estimates and are combined after taking square roots.
  • B.4 A level-ℓinequality, and the leakage of one cell: The low-degree contribution is bounded by 2C1α^2s^2/(n−1) when the cell is sufficiently small relative to n.Here s = ln(e/α), and the geometric-series ratio is made at most 1/2 by choosing the universal constant small enough.

B.5 Proof of the one-way rate

The proof bounds the protocol advantage by partitioning the sphere into message cells and summing Lemma B.4 across cell-size regimes. Degenerate ranges are handled separately, and the remaining contributions are each O(n^-1/2).

  • B.5 Proof of the one-way rate: Long messages are handled because when L ≥ c√n, the proposition’s right-hand side exceeds 1.The proof sets c := c0/(4 ln 2).
  • B.5 Proof of the one-way rate: The proof assumes n ≥ n0, while the finitely many cases n < n0 are absorbed by enlarging the constant.This establishes the bound uniformly after fixing a universal n0.
  • B.5 Proof of the one-way rate: Large cells are replaced by complements when their measure exceeds 1/2, and the remaining cells are summed in two size ranges.Very small cells use the cruder Lemma B.4 bound; larger cells use the sharper bound and scale counting.
  • B.5 Proof of the one-way rate: Each of the three main contributions is O(n^-1/2), yielding the proposition’s claimed bound.The proof combines the contributions after treating the relevant cell-size ranges.

C Deferred proofs

This appendix collects two auxiliary statements used locally: a counting argument behind the classical-query comparison and a reference-copy result.

  • C Deferred proofs: The appendix isolates a counting argument used to call classical queries the easy case and contrasts it with coherent classical-oracle queries.It also records a side result on reference copies quoted elsewhere in the paper.

C.1 Classical queries do not synthesize

Classical oracle queries cannot synthesize an arbitrary target state with only polynomially many queries. A counting argument reduces the possible outputs to a small finite family, and a Haar-random state avoids that family.

  • C.1 Classical queries do not synthesize: With T ≤ 2^m − m − 3 classical queries, some m-qubit state has overlap at most 3/4 with every oracle-dependent output state.The proposition applies to every Boolean oracle g and includes circuits with ancillas and oracle-independent random seeds.
  • C.1 Classical queries do not synthesize: The same target state is at trace distance at least 1/4 from every such output, including for every polynomial T = poly(m).The trace-distance conclusion follows from the overlap bound.
  • C.1 Classical queries do not synthesize: Fixing the random seed makes the adaptive transcript a function of a T-bit answer vector, so the possible conditional outputs form a family of at most 2^T states independent of g.This finite-family reduction is the core counting step.
  • C.1 Classical queries do not synthesize: A Haar-random target state has small overlap with that family by a union bound, and averaging over seeds yields one fixed state with the required guarantee.The query bound makes the union-bound exponent at most −2.

C.2 Reference copies accumulate as a random walk

Reference copies distinguish the two states through a swap-sum observable whose signal grows linearly in q while fluctuations grow as √q. This gives matching attack and average-case upper-bound rates up to logarithmic factors.

  • C.2 Reference copies accumulate as a random walk: The separation argument is independent of this side result, while the reference-copy rate is described as √q rather than q up to a logarithm.The underlying swap operator is the Jucys–Murphy element, with the counting lemma serving as an elementary substitute for spectral information.
  • C.2 Reference copies accumulate as a random walk: The proposition gives an attack with bias at least 1/80√(q/log^2(4n))/n for every half-dimensional H.The effect depends only on n and q and works pointwise in H.
  • C.2 Reference copies accumulate as a random walk: Every H-independent effect has average bias at most C√(q log(2n))/n, matching the attack up to logarithmic factors.The upper bound holds in the stated reference-copy setting.
  • C.2 Reference copies accumulate as a random walk: The moment analysis uses a walk-counting lemma: fresh indices push the permutation away from identity, while repeated indices can move it back.The resulting tradeoff controls even moments of the swap sum.
  • C.2 Reference copies accumulate as a random walk: The swap-sum X has mean gap 2q/n between the two states, while its fluctuations are of order √q under both states.Truncating X at the fluctuation scale and thresholding produces the attack.

D The sharp rate for the half-subspace pair

The sharp-rate analysis bounds distinguishers for the half-subspace pair by poly(λ)·n^−1/2, including polynomial classical queries, advice, and reference copies, while separately accounting for the final coherent query.

  • poly(λ)·n^−1/2 bounds the half-subspace pair against the stated hybrid adversaries, and this rate is optimal up to polynomial factors.The appendix achieves the same rate without a communication bound, using linearity in the hidden reflection.
  • At n = 2^λ, polynomial q, L, a, and log M yield exponentially small distinguishing advantage.The bound remains 2^−Ω(λ) when the advice dimension satisfies d_A ≤ n^(1−ε).
  • With no coherent query, the bound becomes poly(λ)·n^−1/2 and specializes at L = a = q = 0 to the base half-subspace theorem.The explicit no-coherent-query form is 2q(L + a + 1)/(n − 2q).
  • Reference copies reduce the residual dimension and contribute a 2q/n loss before the half-subspace analysis is applied.Conditioning on the classical spans of the reference copies produces a mixture of a known branch and a residual Haar-random half-subspace branch.
  • The proof converts the final coherent-query advantage into a convex combination of one-query expressions and bounds their weighted norms uniformly.The record identity and nonnegative weights enable the convex-combination step, after which concentration controls deviations from the means.
  • The sharp hybrid theorem also applies to the enlarged hidden object because its record identity, reflection dependence, and Boolean truth-table coverage persist.
Loading 2609.11901v1…