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

Whether EFI pairs imply one-way puzzles is open. We construct a classical oracle and analyze its security using communication complexity and random matrix tools. Relative to it, one-way puzzles do not exist, while EFI pairs remain secure against coherent-last distinguishers.

  • Problem

    Whether EFI pairs imply one-way puzzles remains open, leaving unresolved whether indistinguishability of quantum states entails hardness of a classical average-case search problem.

    Source: §1 · p. 3

  • Method

    We construct an oracle that hides a Haar-random subspace and answers sampler-output probability queries, using communication-complexity bounds for classical access and matrix concentration for coherent access.

    Source: §1.1 · pp. 4–5

  • Results

    Relative to the oracle, one-way puzzles do not exist even with an unbounded verifier, while an EFI pair remains secure against coherent-last distinguishers.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The separation shows that a relativizing argument cannot derive a one-way puzzle from an EFI pair in general.

    Source: §1 · p. 3

    The security argument admits only O(λ)-qubit quantum advice; its scope does not cover coherent access before a classical transcript or two coherent queries.

    Source: §1.2 · p. 12

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 introduction situates the question of whether EFI pairs can exist without one-way puzzles among prior work and previews an oracle separation, outlining how counting and communication- and query-complexity bounds address classical-output hardness and quantum-state indistinguishability. It also discusses the proof’s limits under coherent access and notes that the probability-estimation construction requires an H-dependent counting oracle that could leak H.

1 Introduction

  • EFI pairs [BCQ23] and one-way puzzles [KT24] are candidate minimal assumptions: puzzles imply EFI pairs, but whether EFI pairs imply puzzles remains open.EFI pairs concern indistinguishability of quantum states, while one-way puzzles concern classical average-case search hardness.Source: §1 · p. 3

1.1 Main results

  • A deterministic Boolean oracle O′ eliminates one-way puzzles even against unbounded verifiers, while an efficiently generatable half-subspace pair has TD ≥ 1−2^-Ω(λ) and coherent-last distinguishing advantage 2^-Ω(λ).The puzzle attack is classical and applies even with full coherent access; the EFI security guarantee is for coherent-last access.Source: §1.1 · p. 5
  • Relative to O′, a classical-query classical party simulates any quantum polynomial-time party in a classical-message protocol to within 2^-λ transcript distance, ruling out proofs of quantumness against unbounded verifiers.The simulation assumes no entanglement or other correlated setup shared in advance and is uniform in the counterparty.Source: §1.1 · p. 6
  • Theorem C bounds average distinguishing advantage by 2βΠ(L + a + 1), reducing classical oracle leakage to communication complexity for any deterministic oracle, however powerful.For the half-subspace pair, the relevant Vector-in-Subspace problem is easy quantumly but has randomized classical communication complexity Ω(n^1/3), even with two-way interaction and shared randomness [KR11].Source: §1.1 · pp. 6–7
  • Theorem D also bounds coherent-query extensions: advice of dimension n^{2−ε} with one query of any width, or two queries with a first of width n^{2−ε}, gives bias 2^-Ω(λ).The full coherent-last security result additionally allows polynomially many adaptive classical Count queries, reference copies, and classical or linearly many qubits of advice.Source: §1.1 · p. 7

1.2 Technical overview

  • The oracle combines hidden-subspace states with exact sampler-output probability answers; classical single-bit leakage lets the pair remain hidden while probabilities become easy to estimate [Cav+25c] [HM25].The counting oracle uses ranked queries to avoid circularity when samplers themselves query the oracle.Source: §1.1 · p. 4, §1.2 · p. 8
  • Exact probability bits let a classical adversary conditionally sample puzzle keys, ruling out one-way puzzles even against an unbounded verifier, and make classical-output sampler pairs statistically as easy to distinguish as computationally.The same attack rules out QEFID pairs; the adversary need not run the verifier.Source: §1.2 · p. 9
  • Classical oracle transcripts reduce to two-party protocols for Vector-in-Subspace, with small-advantage bound β(n, L) ≤ (L + 1)/n^(1/3), but this argument excludes coherent access.The reduction charges for transcript length and advice, not oracle computation; quantum side information about the hidden subspace is outside its scope.Source: §1.2 · p. 10
  • For one coherent query, the spectral bound is O(sqrt(log(2M)/n); combined with classical queries and advice, it preserves negligibility but does not cover unrestricted coherent access.The combination allows O(λ)-qubit advice; larger advice, a coherent query before the transcript, and two coherent queries remain outside the proof. The oracle’s state-source construction is finally encoded in a Boolean function.Source: §1.2 · pp. 12–13

1.3 Comparison with Lombardi–Ma–Wright

  • The proof adopts the query-mass weighting and operator-norm reduction of [LMW24], but uses curvature-based matrix concentration because a Haar-conjugated reflection lacks independent entries.The ensembles are suited to different conclusions: [LMW24] uses efficiently preparable phase states, while this construction stores Haar-random data in a Boolean function and eliminates one-way puzzles.Source: §1.3 · pp. 13–14

1.4 The question of fully coherent access

  • Conjecture 8.2 asks whether the separation persists under fully coherent access; if it fails, coherent access with polynomial classical advice exceeds the classical-transcript ceiling O(poly(λ) · n^−1/6).At small width, a union bound settles the conjecture when M + a ≤ n^(2−ε); further bounds cover quantum advice of dimension n^(2−ε) with one query and two adaptive queries whose first width is n^(2−ε). The open regime is T ≥ 2 at widths n^(2−o(1)) and above.Source: §1.4 · p. 15

1.5 Related work

  • In the primitive taxonomy of [Gol+24], the result separates NanoCrypt from CountCrypt when adversaries query Count classically except for one final coherent query.Source: §1.5 · p. 15
  • The counting oracle removes the probability-estimation hardness characterized for one-way puzzles [Cav+25c] [HM25]; nonexistence under counting power was already known from BQP = PP and a PP-oracle attack [Gol+24] [Cav+25b].The proposed attack follows the conditional-sampling idea behind the forward direction of the characterization.Source: §1.5 · pp. 15–16
  • Eliminating one-way puzzles through probability estimation requires an H-dependent counting oracle that could leak H and undermine the pair; OWPuzzs can also arise from #P-hardness and quantum advantage [KT25].The oracle removes the hardness those constructions rely on.Source: §1.5 · p. 16
  • No implication from EFI to P̸ = PSPACE is known; the PP-oracle attack [Kre21, Thm. 27] uses O(λ) copies and does not establish single-copy security.The cited frontier also includes a classical oracle with P = NP and single-copy pseudorandom states, and an EFI result up to O(log λ) advice [Cav+25a]; copy amplification [BZ26] does not close the gap.Source: §1.5 · p. 16
  • Earlier work gives a unitary oracle with EFI and QEFID pairs but no OWSGs [Beh+25], the opposite orientation because it retains OWPuzzs; this separation needs no CHRS-to-unitary lifting [GZ25].The paper’s Theorem 7.2 already gives a single classical oracle.Source: §1.5 · p. 16
  • The security argument routes a quantum-state pair’s classical-query-oracle security through a communication lower bound for VSP, building on information-complexity and one-way protocol results [KR11; Ker+12; Raz99; Mon19, App. A; GS19; Gav+07].The paper identifies this as the first such reduction; the cited work gives an O(√n) one-way protocol and an Ω(√n) lower bound on gapped instances.Source: §1.5 · p. 16

1.6 Organization

  • The paper develops the communication reduction, defines the oracle, proves EFI security, establishes coherent-query and hybrid bounds, and gives the deterministic classical-oracle separation.It then states a conjecture about the standard quantum oracle model and collects open problems.Source: §1.6 · pp. 16–17

2 Preliminaries

The preliminaries define the hidden half-subspace states, query model, security notions, and conventions, and establish a classical communication lower bound for Vector-in-Subspace. The bound follows from Theorem 2.6, with the zero-communication case handled separately.

2.1 Notation

  • The notation sets λ as the security parameter and n = 2^λ as the dimension, while defining logarithms, indicator functions, and total variation distance.The arguments require n to be even and 2^Θ(λ); the two bounds serve different purposes.Source: §2.1 · p. 18

2.2 Operators and effects

  • Effects capture any computationally unbounded two-outcome distinguisher, while operator norms, purification, Hermitian dilation, and nets provide tools for the analysis.For an effect E and state ρ, the acceptance probability is Tr(Eρ).Source: §2.2 · p. 18

2.3 Haar-random subspaces and the half-subspace pair

  • A Haar-random n/2-dimensional subspace defines orthogonal-support states that are perfectly distinguishable with its projector measurement, and their acceptance-probability gap is a linear statistic of its reflection.The construction uses the real ensemble; the Section 6 estimates transfer from the complex ensemble with a change in universal constant.Source: §2.3 · p. 19

2.4 The query model

  • Algorithms are modeled as effects depending on the oracle truth table; a single phase query is represented by pre-query isometry, oracle action, and post-query effect.The bit-flip and phase-query models are equivalent up to a factor of 2 in width.Source: §2.4 · p. 20

2.5 EFI pairs and one-way puzzles

  • EFI pairs require efficient generation, statistical farness, and computational indistinguishability; this construction’s pair is secure under classical advice and stronger specified advice regimes [BCQ23].It remains outside the stated security guarantee when polynomial-size quantum advice is combined with classical queries; one-way puzzles permit computationally unbounded verification [KT24] [Cav+25c].Source: §2.5 · pp. 20–21

2.6 Classical communication complexity

  • Classical communication protocols charge only exchanged message length, allow unbounded local computation, and have transcript sets that form rectangles in the parties’ inputs.The paper uses the model because the party holding the hidden subspace must answer arbitrary queries.Source: §2.6 · p. 22

2.7 The Vector-in-Subspace problem

  • Every classical randomized two-way shared-randomness protocol for VSP_n with worst-case error at most 1/3 communicates at least c n^1/3 bits [KR11]; its small-advantage bound is β(n, L) ≤ C(L + 1)/n^1/3.VSP_n asks classical communicators to decide whether a vector lies in a subspace or its orthogonal complement; β(n, 0) = 0.Source: §2.7 · pp. 22–23
  • Theorem 2.6 forces the cost to be large, yielding the bound on ε.The supplied passage does not state the bound’s formula.Source: §2.7 · p. 23
  • With no communication, the output is independent of b, so β(n, 0) = 0; replacing L with L + 1 absorbs this case at constant cost.Bob’s uniform input H is independent of b, and Alice’s marginal vector u is sphere-uniform regardless of b.Source: §2.7 · p. 24

3 Security from communication complexity

When all information about the hidden object reaches an adversary through classical data, its distinguishing power is bounded by a two-party classical communication problem, regardless of the oracle’s power. A communication gap between classical hardness and statistical distance therefore yields pairs secure against classical transcripts, though the reduction does not cover coherent queries.

3 Security from communication complexity

  • The reduction simulates the distinguisher as Alice and the hidden-object holder as Bob, who supplies advice and answers classical oracle queries; Alice’s quantum computation can be simulated by classical randomized communication.The challenge is given to Alice as a classical description, and the transcript plus advice costs at most L + a + 1 bits.Source: §3 · pp. 24–25
  • The bound covers fully adaptive classical queries by charging total transcript length, but not coherent access, quantum advice depending on X, or an oracle that measures the challenge.Even an oracle returning only a classical bit can distinguish the pair with certainty if it receives the challenge as quantum input.Source: §3 · pp. 25–26

The quantum upper bound

  • If the expected trace distance is at least δ, the associated problem has a quantum protocol where Alice sends ⌈log2 d⌉ qubits and Bob returns one classical bit, with advantage at least δ/2.Bob holds X and applies the Helstrom measurement to Alice’s sample.Source: The quantum upper bound · p. 26

3 Security from communication complexity

  • For any deterministic oracle and distinguisher using L bits of classical query traffic and a bits of classical advice, average advantage is at most 2βΠ(L + a + 1).The oracle may be computationally unbounded or encode the hidden object; the bound depends on the length of the classical transcript and advice.Source: §3 · pp. 24–25, The quantum upper bound · p. 26

The quantum upper bound

  • If βΠ(ℓ) ≤ γ(ℓ) and the pair’s expected trace distance is at least δ, every such distinguisher has advantage at most 2γ(L + a + 1), while the pair remains usable with quantum advantage δ/2.The bound applies to every deterministic oracle, however powerful.Source: The quantum upper bound · p. 26
  • The criterion requires a classically hard associated problem and statistically far states; its quantum communication protocol is always logarithmic-cost, so that side of the gap must remain inaccessible.The reduction applies only when the associated problem is hard for classical communication at small advantage.Source: The quantum upper bound · pp. 26–27
  • The reduction is one-directional: Alice’s classical challenge description can make the associated problem easier than distinguishing a single copy, so classical hardness suffices for security but is not necessary.If branch descriptions differ, a zero-communication protocol can read b from its input, while a one-copy distinguisher is bounded by trace distance.Source: The quantum upper bound · p. 27

4 The oracle and the primitives it removes

Section 4 constructs an oracle from a Haar-random subspace state source and a ranked exact-probability-bit oracle, and shows how it removes one-way puzzles and classical-output decision hardness. It also establishes classical simulation of interactive quantum behavior under classical-message restrictions for every fixing of the hidden subspaces, while distinguishing the remaining quantum-state indistinguishability from classical-output hardness.

4.1 The state source

  • The state source samples fresh Haar-random pure states from orthogonal half-dimensional subspaces, whose density operators have trace distance 1.The source doubles as the public EFI generator by returning a state indexed by the classical branch bit.Source: §4 · p. 27, §4.1 · p. 28

4.2 The counting oracle

  • Count returns exact output-probability bits, and a rank restriction makes its recursively defined oracle unique and well-defined.A rank-r query refers only to samplers using lower-ranked layers, avoiding the inconsistency of unrestricted self-reference; the oracle's computational power is irrelevant to the security argument.Source: §4.2 · pp. 28, 30

4.3 Nonexistence of one-way puzzles

  • t classical Count queries estimate any QPTO-samplable classical distribution's probabilities with additive error 2^-t and success probability 1.The estimator uses a rank bound read from the sampler's explicit step bound.Source: §4.3 · pp. 30–31
  • For every correct one-way puzzle relative to O, a polynomial-time classical adversary using classical Count queries succeeds even against an unbounded verifier.It samples keys from exponentially accurate conditional-distribution estimates, making the puzzle-and-key distribution 2^-λ-close to honest and acceptance 1 − negl(λ); it never runs the verifier.Source: §4.3 · p. 32
  • The oracle also excludes multi-copy pseudorandom states, pseudorandom unitaries, pure-output one-way state generators, and pure-banknote quantum-money mini-schemes, each of which implies one-way puzzles [KT24] [BJ24] [KT25] [MY22].The classical adversary also rules out classically secure one-way puzzles relative to O.Source: §4.3 · p. 32

4.4 Nonexistence of QEFID pairs

  • The same oracle removes classical-output indistinguishability as well as the classical-output one-wayness in the one-way-puzzle definition.Source: §4.4 · p. 33
  • A classical polynomial-time distinguisher using O(ℓ+λ) Count queries achieves advantage at least TV(D0,D1)−2^-λ for any two QPT classical-output samplers.The bound holds for every fixing of {Hλ}; thus computational and statistical indistinguishability coincide for these sampler distributions.Source: §4.4 · p. 33
  • Relative to O, QEFID pairs do not exist, and no classically secure QEFID pair survives the classical-query attack.The direct quantitative argument rules them out for every fixing of {Hλ}; it also excludes EFI pairs diagonalizable by a QPT isometry whose Count queries are classical and whose registers are retained.Source: §4.4 · p. 34

4.5 Interactive protocols with classical messages

  • For any quantum party exchanging only classical messages, a classical Count-query party simulates its transcript within 2^-λ total variation against every counterparty.The counterparty may be computationally unbounded and query O; the parties must have no shared entanglement or correlated setup.Source: §4.5 · pp. 35–36
  • Consequently, QPTO-samplable classical distributions have classical Count-query samplers within 2^-λ total variation, and no inefficient-verifier proof of quantumness exists.For any QPTO prover and unbounded classical-message verifier, a classical polynomial-time prover can match its acceptance probability within 2^-λ.Source: §4.5 · p. 37
  • The collapse covers interactive classical-message protocols, but not quantum messages or prior entanglement; quantum-state indistinguishability remains available relative to O.Count removes classical-output search, decision, and interaction hardness, while Theorem 5.5 supplies a surviving pair of indistinguishable quantum states.Source: §4.5 · p. 38

5 EFI security

The section establishes security for the half-subspace EFI pair by reducing reference-copy security to classical Vector-in-Subspace, and characterizes the optimal advantage of classical measure-then-count adversaries. It sharpens VSP communication bounds, giving one-way rates at every message length while identifying a limitation in the two-way bound.

5.1 Reference copies and the residual instance

  • Classical spans of q Haar reference copies let an adversary resample the copies and leave Haar half-dimensional VSP in n−2q dimensions, with penalty 2q/n and bound 2q/n + 2β(n−2q,L+1).The bound applies when q < n/4; the 2q/n penalty is the conceded known-subspace branch.Source: §5.1 · p. 39

5.2 The security theorem

  • With probability one over Hλ, the half-subspace ensembles form an EFI pair secure against QPT distinguishers with public R, adaptive classical Count access, and arbitrary oracle-dependent polynomial classical advice.Countable machine enumeration and maximizing over advice inside the expectation let average security yield a fixed sequence {Hλ} secure against all such adversaries.Source: §5.2 · pp. 40–41
  • An oracle with source R eliminates one-way puzzles, including inefficiently verifiable and classically-secure ones, and QEFID pairs, while the half-subspace EFI pair remains secure with one final coherent Count query.The stated access model allows polynomially many adaptive classical Count queries, then one coherent query of width 2poly(λ), and polynomial classical advice depending on the fixed oracle.Source: §5.2 · p. 42

5.3 The optimal advantage of a classical adversary

  • For Haar-random H of dimension n/2 (n ≥ 4), measure-then-count distinguishing advantage is 2(πn)^-1/2(1 + O(n^-1)), attained by computational-basis measurement with polynomially many classical Count queries.Source: §5.3 · p. 43
  • Classical-adversary security requires superpolynomial n; its advantage is bounded by O(poly(λ) · n^-1/6), while an attack achieves Ω(n^-1/2).Both bounds are 2^-Θ(λ) for the chosen n = 2^Θ(λ); Appendix D improves the upper bound to poly(λ) · n^-1/2, so the gap is a feature of the communication route, not the pair.Source: §5.3 · p. 44
  • The counting oracle’s information about H and one coherent query each attain advantage at scale n^-1/2.Even exact outcome probabilities for an arbitrary measurement do not exceed that scale; a one-query attack meets Theorem 6.6 within √log n.Source: §5.3 · p. 44

5.4 The one-way rate for VSPn

  • For one-way protocols on the exact Haar-distributed VSPn promise, βow(n, L) ≤ C(L + 1)/√n, yielding Θ(√n) bits at constant advantage.The upper bound holds at every message length; Raz’s one-way protocol gives the matching upper communication bound, with a published proof in [Mon19, App. A].Source: §5.4 · pp. 44–45
  • For two-way VSPn protocols, β(n, L) ≤ C 2^(L/2)/√n, a bound that is stronger than the corruption bound only for very short transcripts.The second-moment bound is stronger for L ≤ 2/3 log2 n; the general two-way small-advantage question remains open.Source: §5.3 · p. 44, §5.4 · pp. 45–46
  • Proposition 5.10 handles arbitrary measurable partitions without a rank restriction, unlike the open concentration conjecture relevant to two-way protocols.Its one-way proof uses a first-moment bound over cells and a second-moment computation; the cited conjecture remains open, and neither Klartag and Regev [KR11] nor Grupel [Gru17] treats the small-advantage regime.Source: §5.4 · p. 46

6 Coherent queries

Section 6 bounds adversarial access to the hidden subspace through coherent queries and quantum advice, establishing EFI security when classical oracle queries precede a final coherent query and extending the analysis to polynomially many challenge copies and bounded advice. It also identifies the classical-transcript condition limiting the method and gives bounds on coherent-query attacks, including an attack showing the one-query bound is tight up to a logarithmic factor.

6 Coherent queries

  • An exact-real oracle encoding projector entries lets one uniform-superposition query produce orthogonal states for distinct hidden projectors; finite-precision Boolean oracles are covered by Theorem 6.6.An exact-real register with orthogonal states for distinct values is non-separable; rounding to finite precision yields a Boolean oracle of width 2^poly(λ).Source: §6 · p. 47

6.1 Concentration of measure on the classical compact groups

  • Scalar concentration makes the bias negligible for M = O(n^(2−ε)), but its union bound fails at the much larger widths required by the model.The subsection turns instead to curvature-based matrix concentration to control the maximum over truth tables without a union bound.Source: §6.1 · p. 48

6.2 A variance bound for linear statistics of a Haar-conjugated observable

  • For an M × M matrix of linear statistics of one Haar-conjugated observable, the row and column hypotheses yield an operator-norm bound costing only a √log(2M) factor.This variance bound extends the concentration framework to large M without requiring independent matrix entries.Source: §6.2 · p. 50

6.3 The one-query bound

  • A single coherent query has bias O(√(log(2M)/n)) for every Boolean function of the hidden subspace.The proof removes the truth table by normalizing the query-label weights, then bounds the resulting random matrix’s expected operator norm.Source: §6.3 · p. 52
  • At width 2n, a one-query attack achieves bias at least (4πn)^−1/2, while the upper bound is C√(log(4n)/n), tight up to √log n.The attack measures the challenge in the computational basis and makes one classical query; the bounds hold in both the complex and real ensembles.Source: §6.3 · pp. 53–54
  • For t parallel coherent queries of width M, average bias is at most C√((t log(2M)+1)/n), hence negligible for polynomial t and width when n=2^Ω(λ).The bound follows by treating the parallel queries as one query to a wider oracle.Source: §6.3 · p. 54

6.4 Quantum advice

  • An unbounded distinguisher given m H-dependent advice qubits and one challenge copy, but no oracle queries, has average bias at most C′√m/n + 1/n, negligible for m=n^{2−Ω(1)}.The proposition’s bound holds for arbitrary advice families, without measurability or computability assumptions.Source: §6.4 · pp. 54–55
  • Any polynomial-qubit H-dependent advice state with one challenge copy gives an unbounded, no-query distinguisher only negligible bias, equivalently resisting polylog(n)-qubit one-way quantum advice in VSP.The proof synthesizes the advice using one query to a Boolean function of H, then applies the coherent-query bound and charges the synthesis error.Source: §6.4 · pp. 56–57
  • At O(n log n) classical bits, a classical-input VSP receiver succeeds with probability 1−o(1), while a receiver with one challenge copy and the same-size quantum advice has bias o(1).The stated separation is by a factor Ω(n/log n); it concerns distinct receiver models and does not apply to the classical-input model’s stronger party holding u.Source: §6.4 · p. 57
  • For reverse one-way VSP communication, Bob needs Ω(n) qubits for constant advantage, and O(n) classical bits suffice, giving Θ(n) complexity.Source: §6.4 · p. 57
  • One-copy quantum advice requires m = Θ(n^2), while classical descriptions of q reference-state spans achieve 2q/n for q ≤ n/2 and are quadratically stronger than the states themselves.At m = q⌈log2 n⌉ advice qubits, the sample-based random walk achieves the √m rate up to logarithmic factors.Source: §6.4 · p. 58
  • Fresh b = 0 reference-state samples provide an advantage of e^Θ(√q)/n, both as an attack and as an upper bound.Each copy couples to the challenge through a swap whose mean shift is 2/n against unit-size fluctuation.Source: §6.4 · p. 58

6.5 Classical queries followed by one coherent query

  • For q < n/4, Theorem 6.13 bounds adversaries with classical advice, reference copies, adaptive classical queries, and one final coherent query; for n = 2^Ω(λ) and polynomial parameters, the bound is 2^-Ω(λ).The theorem allows otherwise unbounded computation and coherent-query width M; its bound depends on log(2M), the classical-query budget, and the advice length.Source: §6.5 · p. 59
  • The hybrid proof separates an H-independent final operation, bounded by communication complexity, from the H-dependent coherent-query increment, controlled using concentration.The classical transcript conditions on H, so the proof hard-wires query answers into H-independent record operators and uses concentration to handle the resulting records.Source: §6.5 · pp. 59, 61
  • For k challenge copies, a single-challenge reduction has advantage Adv(D)/k, so the security bounds remain negligible for polynomial k.The reduction uses k−1 reference copies of each state; this hybrid works because the EFI game supplies both reference states.Source: §6.5 · pp. 63–64
  • Quantum advice is handled by encoding a net index as classical advice, allowing Theorem 6.13 to apply to the adversary’s prepared advice state.The enlarged classical advice length is a′ = a + ⌈2dA log2 9⌉.Source: §6.5 · p. 64
  • With n = 2λ and polynomial q, L, a, and log M, security remains 2^-Ω(λ) for quantum advice dimension dA ≤ n^(1/3−ε), or up to (1/3−ε)λ qubits.The bound also applies to the enlarged object X = (H, S) of Section 7.Source: §6.5 · p. 64
  • The method requires classical transcript information between the state source and the final coherent query; it does not cover interleaved queries or two full-width coherent queries.A coherent query first can synthesize quantum advice about H, while two coherent queries require Conjecture 8.2.Source: §6.5 · pp. 64–65

7 The separation relative to a single classical oracle

The section constructs one deterministic classical oracle that eliminates one-way puzzles while retaining a half-subspace EFI pair against coherent-last distinguishers. It also rules out coherent-last fully black-box constructions of one-way puzzles from EFI pairs.

7.1 The oracle and the generator

  • O′ combines Count with a total Boolean G storing one-query generators for rounded samples from H and H⊥; G′ hides each sample index by discarding it.The samples are rounded to a finite net to ensure the oracle is a measurable function of the hidden object.Source: §7.1 · pp. 65–66

7.2 The separation theorem

  • With probability one, O′ has no one-way puzzles, including inefficiently verifiable and classically-secure ones, or QEFID pairs, while G′ yields an EFI pair indistinguishable with advantage 2^-Ω(λ).The pair is efficiently generated and statistically far.Source: §7.2 · p. 66
  • The proof replaces stored references and the challenge with fresh samples before the communication reduction; otherwise Bob could identify Alice’s challenge from S, and fresh samples restore the spectral and span arguments.The stored pair’s empirical difference does not satisfy the spectral bound, and resampling stored references from their spans would not reproduce their joint law.Source: §7.2 · pp. 66, 69

7.3 The black-box barrier

  • No fully black-box construction of one-way puzzles from EFI pairs exists when its reduction remains a QPT distinguisher with classical advice and coherent-last access.The corollary follows because the oracle admits a classical puzzle inverter, while the corresponding EFI pair remains indistinguishable to that distinguisher class.Source: §7.3 · p. 70

8 Fully coherent access

This section examines EFI-state security under fully coherent oracle access, conjecturing negligible bias for polynomially bounded access while proving unconditional security in several restricted-width regimes and tracing the implications for the oracle separation. It also explains why a cheap quantum Vector-in-Subspace protocol is not itself an attack with the available oracles, whereas a controlled reflection would be a different capability enabling deterministic distinguishing.

Conjecture 8.2

  • Conjecture 8.2 predicts negligible average bias for polynomially bounded adaptive coherent queries, advice, reference copies, and query width, even for any Boolean function of the hidden object.The adversary receives one challenge copy; the conjecture also permits fresh reference copies and classical advice.Source: §8 · p. 71

Lemma 8.3

  • Reference copies can be removed by reducing dimension from n to n − 2q̄, at a bias loss of at most 2q̄/n.The resulting adversary keeps one challenge copy, the same query count and width, and the same number of classical advice bits.Source: §8 · p. 72

Proposition 8.4

  • For any query count, the conjecture’s conclusion holds unconditionally when M + a ≤ n^(2−ε), for each fixed ε > 0.Here M is the query-label set size and a is the number of classical advice bits.Source: §8 · p. 72

Proposition 8.5

  • With one coherent query, quantum advice of at most (2 − ε)λ qubits still gives average bias 2^-Ω(λ) when log M is polynomial in λ.This bound allows advice depending arbitrarily on H.Source: §8 · p. 73

Proposition 8.6

  • Two adaptive coherent queries have negligible bias when the first width M1 ≤ n^(2−ε) and log M2 is polynomial in λ, however large M2 is.The restriction on the first query’s width is used to bound the contribution across its possible truth tables.Source: §8 · p. 74

The first open case

  • Two coherent queries can encode arbitrary polynomial-size quantum advice plus one coherent query, leaving the case of advice exceeding linearly many qubits unresolved.Proposition 8.5 settles the advice dimension up to n^(2−ε); the section identifies the absence of a classical record for conditioning as an obstacle beyond that regime.Source: §8 · p. 75

Proposition 8.7

  • If the polynomial form of Conjecture 8.2 holds, the separation extends to fully coherent access and removes the advice restriction; if it fails, Proposition 8.7 yields a polynomially bounded attack exceeding the classical-transcript ceiling.The no-one-way-puzzle direction needs no further argument because its attack is classical.Source: §8 · pp. 75–76

Case (B) and its scope

  • Case (B) gives an inverse-polynomial-bias attack against the classical ceiling, but does not by itself break O′ under coherent access.Its bias is the trace quantity displayed in the passage, compared with the classical ceiling using Lemma 2.7 at L = poly(λ).Source: §8 · p. 76

Limits of the reflection attack

  • The reflection attack does not resolve the Unitary Synthesis Problem: it gives inverse-polynomial bias for one ensemble, not inverse-exponential synthesis error over all unitaries.The passage also notes that the attack is query-efficient, whereas the problem asks for circuit efficiency; reflection-supplying oracles are not Boolean functions of H answering in classical bits.Source: §8 · pp. 76–77

The quantum protocol for VSP

  • The O(log n)-qubit quantum protocol for VSP does not break the pair because the holder of H must perform the measurement, which neither oracle provides.Alice sends |u⟩, but Bob applies {PH, PH⊥}; the adversary cannot make the oracle perform that measurement on the challenge.Source: §8 · p. 76

Query-to-message direction

  • A cheap quantum protocol rules out a communication-based security proof under coherent access, but yields no attack without a way for the holder of H to act on the challenge.The query-to-message correspondence supports the lower bound, while reversing it would require a reflection oracle or quantum-input channel.Source: §8 · pp. 76–77

Reflection-oracle attack

  • With a controlled reflection oracle, an adversary distinguishes the challenge bit deterministically by converting the reflection’s global sign into an ancilla measurement.The challenge lies in the (−1)^b eigenspace; controlled-RH followed by a Hadamard and measurement returns b.Source: §8 · p. 77

9 Discussion and open problems

Classical resources map to communication complexity and remain below the VSP threshold, while coherent access and mixed quantum/classical resources expose limits of the current security arguments. The discussion identifies open problems in coherent-query security, VSP complexity, quantum advice, and oracle extensions.

Discussion and open problems

  • Classical Count queries and oracle-dependent classical advice correspond to classical communication below the VSP threshold, with leakage bounded by Θ(n^-1/2) for measure-then-count and poly(λ)n^-1/6 in general.Quantum advice is a one-way quantum message to the holder of one challenge copy, with threshold m = Θ(n^2) qubits.Source: §9 · p. 77
  • Conjecture 8.2 asks whether the pair survives polynomially many adaptive coherent queries; the access model proven secure allows a polynomial classical transcript followed by one coherent query.The first open case is two coherent queries, where the relevant widths are n^{2−o(1)} and above; the conditioning argument fails because quantum advice and coherent queries provide no classical record to average over.Source: §9 · pp. 77–78
  • Classical VSP complexity remains between n^1/3 and √n, while a two-way bound O((L + 1)n^-1/2) would sharpen security to the exact exponent.Raz’s protocol gives the upper endpoint [Mon19]; Klartag and Regev’s rectangle-bound assessment is heuristic [KR11]. The current small-advantage bounds are O((L + 1)n^-1/6) and O(2^{L/2}n^-1/2), with Proposition 5.8 ruling out improvement beyond n^-1/2 at L = poly(λ).Source: §9 · p. 78
  • Security against k challenge copies follows from the single-copy result by a hybrid at factor k, but classical communication complexity of k-VSP remains open for every k ≥ 2.The reduction from k vectors to one uniform vector makes k-VSP at least as easy as VSP, and the communication question differs because Alice holds classical descriptions while the receiver holds quantum copies.Source: §9 · p. 78
  • Quantum advice thresholds are Θ(n) or Θ(n^2) in distinct communication models, while polynomial-size advice together with adaptive classical Count queries remains open.Linearly many qubits are admitted alongside the full classical budget, and polynomial-size advice is admitted when it stands alone; the unresolved mixed resource corresponds to an initial quantum message followed by two-way classical interaction.Source: §9 · p. 78
  • Open questions also include whether public-key quantum money with mixed banknotes survives the oracle and whether the counting oracle can be made uniform.The [KT25] reduction yields a mini-scheme with a pure banknote, so it does not cover the mixed notion [AC12]; uniformity would not change the security proof because Theorem 3.2 is indifferent to how the truth table is specified.Source: §9 · p. 78

A The conditional-sampling attack · B The two rates

The appendix shows that exact counting-oracle estimates let a classical attacker sample a puzzle key closely enough to make any correct verifier accept, without running the verifier. It also states that its separate arguments for Proposition 5.8 and the upper bound of Proposition 5.10 are independent and unnecessary for the separation.

A The conditional-sampling attack

  • With exact counting-oracle bits, additive error 2^-t costs t queries, keeping the conditional-sampling analysis elementary.The sampler’s Count-query ranks are bounded by J, and it accesses only O^<J+1.Source: A The conditional-sampling attack · p. 85
  • The attacker builds the key one bit at a time, estimating each next-bit conditional probability with Count queries and sampling from the estimates rounded to multiples of 2^-2t.It uses t = m + ℓ + 3λ, η = 2^-t, and 2mt = poly(λ) classical queries.Source: A The conditional-sampling attack · p. 85
  • The attacker’s joint distribution of puzzle and key is within total variation distance 2^-λ of the honest distribution for all sufficiently large λ.The stated bound is 4mη 2^(ℓ+m) ≤ 2^-λ.Source: A The conditional-sampling attack · p. 85
  • A hybrid argument replaces the attacker’s bit choices with the true conditional law, bounding the per-prefix discrepancy before summing over the m key bits.For prefixes with P(w) ≥ 4η, the per-prefix total variation bound is 4η/P(w); elsewhere the proof uses the trivial bound of 1.Source: A The conditional-sampling attack · p. 85
  • A classical randomized polynomial-time attacker using polynomially many classical queries produces a key accepted with probability 1 − negl(λ), contradicting puzzle security even when the verifier is uncomputable.The attacker never runs the verifier; correctness and closeness to the honest key distribution suffice.Source: A The conditional-sampling attack · p. 86

B The two rates

  • The appendix’s proofs of Proposition 5.8 and Proposition 5.10’s upper bound are independent of each other, and neither is needed for the separation.Source: B The two rates · p. 86

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

A Beta absolute-deviation calculation gives a 2/√(πn) upper bound on the measure-then-count adversary’s advantage for arbitrary POVMs; a computational-basis threshold test asymptotically attains it.

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

  • For a Haar-random real n/2-dimensional subspace, ⟨v|P_H|v⟩ has Beta(n/4,n/4) law, with E|ξ_v|=(πn)^-1/2(1−1/(2n)+O(n^-2)).The upper bound is 1/√(πn); the asymptotic expansion gives the sharper deviation value.Source: §B.1 · pp. 86–88
  • For complex n-dimensional space, a Haar half-dimensional subspace gives Beta(n/2,n/2) overlap, and the same deviation bounds follow with parameter a=n/2.Source: §B.1 · p. 88
  • For real subspaces tested with complex unit vectors, convexity replaces the Beta-law argument and preserves the upper bound E|ξ_v|≤1/√(πn).Writing the vector as x+iy expresses its deviation as a convex combination of two real-case deviations.Source: §B.1 · p. 88
  • For any POVM, the measure-then-count adversary’s advantage is at most 2/√(πn).The bound follows by expanding the POVM effects into eigenvectors and bounding each contribution using the real-subspace estimate for complex vectors.Source: §B.1 · p. 88
  • A computational-basis threshold test using t-bit truncated probabilities attains the POVM upper bound within a factor 1−O(n^-1), with truncation loss O(n^-3/2) when n=2^λ.The exact threshold rule uses the signs of the diagonal deviations; truncation can change decisions only in a narrow window around the threshold.Source: §B.1 · pp. 88–89

B.2 The one-way rate: harmonic analysis on the sphere · B.3 The second-moment operator

The appendices develop spherical-harmonic and heat-semigroup tools, then use them to characterize the second-moment operator for a Haar-random half-dimensional subspace. Its spectral cancellation at degrees divisible by four is also verified directly.

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

  • Spherical harmonics decompose L2(Sn−1, σ) into rotation-invariant degree spaces, on which rotation-commuting operators act as scalars by Funk–Hecke.The cited theorem is Funk–Hecke [Hel00].Source: §B.2 · p. 89
  • The heat semigroup acts on degree-ℓ harmonics by e^(−tℓ(ℓ+n−2)); sphere curvature gives a logarithmic Sobolev inequality and hypercontractivity.The stated logarithmic Sobolev constant is n−2.Source: §B.2 · p. 90

B.3 The second-moment operator

  • For even n≥4 and Haar H of dimension n/2, Lemma B.2 gives ω2=1/(n−1); only degrees ℓ≡2 (mod 4) contribute to the second moment.The scalar of Qs−Qo is zero at degrees divisible by four and equals 2ω2j at degrees ℓ=2j with j odd.Source: §B.3 · pp. 90–91
  • The proof diagonalizes the common-subspace and opposite-subspace two-point operators with Funk–Hecke, then uses Chu–Vandermonde to obtain cancellation at half dimension.At dimension n/2, the two scalars cancel for every degree ℓ≡0 (mod 4).Source: §B.3 · pp. 90–91
  • The product form of ω2j has factors below one, yielding monotonicity and the stated bound on the coefficients.The appendix derives this product form after the spectral calculation.Source: §B.3 · p. 91
  • Elementary moment calculations independently confirm the degree-two value ω2=1/(n−1), which the appendix identifies as dominating downstream estimates.The check uses the second moment of a uniform vector in an m-dimensional subspace and sets m=n/2.Source: §B.3 · p. 91
  • A direct degree-four calculation shows the half-dimensional cancellation vanishes identically, confirming it is not an artifact of the Gegenbauer calculation.The text contrasts this vanishing with the nonzero bracket at other dimensions.Source: §B.3 · p. 92

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

The section proves a sphere level-ℓ inequality using optimized heat-semigroup hypercontractivity, then bounds the leakage of a Haar-random half-dimensional subspace by splitting the spectral sum into low and high levels.

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

  • The level-ℓ inequality is proved by undoing heat-semigroup damping on degree-ℓ harmonics and applying hypercontractivity with an optimized diffusion time.The semigroup scales degree-ℓ harmonics by e^-tℓ(ℓ+n-2); reparameterizing the diffusion time controls the resulting error factors.Source: §B.4 · p. 92
  • For a measurable sphere set A, the expected absolute leakage of a Haar-random half-dimensional subspace is at most 2α, where α = σ(A).Rotation invariance makes the expected measures of A on H and H⊥ each equal α, and the triangle inequality gives the bound.Source: §B.4 · p. 92
  • For small α, the leakage bound splits the spectral sum at j* = ⌈s⌉, with s = ln(e/α), using the level-ℓ inequality below the cutoff and ω decay above it.The low-level terms sum to at most 2C1α²s²/(n −1); the two ranges are then combined and square-rooted to obtain (22).Source: §B.4 · pp. 92–93

B.5 Proof of the one-way rate

The section proves Proposition 5.10’s upper bound by reducing degenerate parameter ranges and summing bounds over the protocol’s message cells.

B.5 Proof of the one-way rate

  • Fixing shared randomness makes Alice’s message a deterministic partition of the sphere, and Bob answers optimally from the cell and H.The proof bounds the advantage by summing Lemma B.4 over cells, split by cell size; very small cells use its cruder bound.Source: §B.5 · p. 93
  • The proof handles long messages by noting the claimed upper bound exceeds 1, absorbs small n into the constant, and replaces any oversized cell by its complement.The long-message reduction applies when L ≥ c√n; at most one cell has measure above 1/2.Source: §B.5 · p. 93
  • For small cells, the entropy and scale-counting bounds yield terms that are each O(n^-1/2).The scale-counting step bounds the number of cells with sm in [k, k + 1) using their measures.Source: §B.5 · pp. 93–94
  • The proof completes the upper bound by combining three contributions and dividing their sum by 4.The final two terms in the cell-size analysis are each O(n^-1/2).Source: §B.5 · p. 94

C Deferred proofs

Appendix C collects two statements used locally elsewhere: the counting argument behind the Section 3 comparison and the reference-copies side result quoted in Section 6.4.

C Deferred proofs

  • The appendix defers the Section 3 counting argument and the reference-copies side result quoted in Section 6.4.Both statements are collected for local use.Source: C Deferred proofs · p. 94

C.1 Classical queries do not synthesize

With at most 2^m − m − 3 classical queries, a circuit’s output remains a constant trace distance from some fixed m-qubit pure state, for every oracle g; in particular, the guarantee holds for T = poly(m).

C.1 Classical queries do not synthesize

  • This counting argument is the classical-query easy case, contrasted with [Ros24, Thm. 4.1], where one coherent query to a classical oracle synthesizes an arbitrary state.Source: §C.1 · p. 94
  • For T ≤ 2^m − m − 3 classical queries, there is a pure m-qubit state |ψ⟩ with ⟨ψ|ρ_g|ψ⟩ ≤ 3/4 and TD(ρ_g, |ψ⟩⟨ψ|) ≥ 1/4 for every oracle g.The proposition also states this applies in particular when T = poly(m).Source: §C.1 · pp. 94–95
  • For each fixed random seed, classical query transcripts yield at most 2^T possible output states, and a Haar-random |ψ⟩ plus a union bound gives a fixed state with average overlap at most 3/4.The transcript is determined by the answer vector, so the candidate output states do not depend on g; the proof bounds their overlap and averages over seeds.Source: §C.1 · pp. 94–95

C.2 Reference copies accumulate as a random walk

With q reference copies, distinguishing the two states yields bias scaling as √q/n up to logarithmic factors, rather than scaling linearly with q. The subsection gives a pointwise attack for every half-dimensional subspace and a matching upper bound on average for H-independent measurements.

C.2 Reference copies accumulate as a random walk

  • For every half-dimensional H, an H-independent effect distinguishes the states using q reference copies with bias at least on the order of √q/n up to logarithmic factors.The attack applies to every fixed H, including real or complex subspaces.Source: §C.2 · p. 95
  • Every H-independent measurement has average bias at most on the order of √q/n up to logarithmic factors, matching the attack’s dependence on q.The upper bound holds in either the real or complex ensemble.Source: §C.2 · p. 95
  • The attack sums the q swaps between reference copies and the challenge: their expectation gap is exactly 2q/n, while fluctuations are at scale √q under both states.Truncating the swap sum at that scale and thresholding yields the distinguishing effect.Source: §C.2 · p. 97
  • Fresh samples of the secret state’s output are worth eΘ(√q)/n, while a classical description of its span is worth Θ(q/n).The comparison places reference copies among the resources about H considered for the pair.Source: §C.2 · p. 98

D The sharp rate for the half-subspace pair

Appendix D proves sharp hybrid security for the half-subspace pair at poly(λ) · n^-1/2, improving the earlier poly(λ) · n^-1/6 rate. It also extends the sharp rate to quantum advice and the enlarged hidden object.

D The sharp rate for the half-subspace pair

  • The half-subspace pair’s security bound improves from poly(λ) · n^-1/6 to poly(λ) · n^-1/2, optimal up to a polynomial by Proposition 5.8.The proof avoids a communication bound by using the linearity of ρ0 − ρ1 = 2R/n in the reflection; unlike Theorem 3.2, this argument does not extend to arbitrary hidden objects.Source: D The sharp rate for the half-subspace… · p. 98
  • At M = 1, Theorem D.1 bounds an adversary with q reference copies per side, L adaptive classical-query bits, and a advice bits, with no coherent query, by 2q(L + a + 1)/(n − 2q).The theorem applies for q < n/4; when n = 2^Ω(λ) and parameters are polynomial in λ, the bound is poly(λ) · n^-1/2.Source: D The sharp rate for the half-subspace… · p. 99
  • For n = 2^λ and polynomial q, L, a, and log M, quantum advice of up to (1−ε)λ qubits still gives a 2^-Ω(λ) bound when dA ≤ n^(1−ε).This improves the admissible advice size from (1/3−ε)λ qubits in Corollary 6.18.Source: D The sharp rate for the half-subspace… · p. 100
  • For the enlarged hidden object X = (H, S), Theorem 7.2 also obtains poly(λ) · n^-1/2, without transferring a communication term.The record identity, reflection-dependent weighted norms, and coverage of queried truth tables by a maximum over Boolean functions all hold in the fresh experiment.Source: D The sharp rate for the half-subspace… · p. 100
Loading 2609.11901v1…