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

Technical Summary: EFI Pairs Without One-Way Puzzles

1. Problem Statement and Motivation

Quantum cryptography currently lacks a single minimal primitive analogous to one-way functions (OWFs) in classical cryptography. Two leading candidates for this minimal assumption have emerged:

1. EFI Pairs (Efficiently preparable, Statistically far, Computationally Indistinguishable): A pair of mixed quantum states that are easy to generate, statistically distinct, but computationally indistinguishable. EFI pairs are equivalent to quantum bit commitments and enable secure multiparty computation.
2. One-Way Puzzles (OWPuzzs): A pair $(Samp, Ver)$ where a sampler generates a classical puzzle $s$ and a key $k$, and an unbounded verifier checks the key. OWPuzzs imply EFI pairs, but the converse is an open question.

The central open problem is whether the hardness required for EFI pairs (indistinguishability of quantum states) necessarily implies the classical average-case hardness required for OWPuzzs (inverting a search problem). Specifically, does there exist an oracle relative to which EFI pairs exist, but OWPuzzs (even with inefficient verifiers) do not?

2. Methodology and Oracle Construction

The author constructs a single deterministic classical oracle $\mathcal{O}'$ that separates these primitives. The oracle consists of two layers:

1. State Source ($R$): On input $(b, 1^\lambda)$, it returns a fresh copy of a mixed state $\rho_{b,\lambda}$. These states are constructed from a Haar-random half-dimensional subspace $H \subseteq \mathbb{R}^n$ (where $n=2^\lambda$). Specifically, $\rho_0$ is the maximally mixed state on $H$, and $\rho_1$ is the maximally mixed state on $H^\perp$.
2. Counting Oracle ($Count$): A classical oracle that, given a description of an oracle-aided quantum sampler $C$ with classical output, returns exact bits of the output probability $\Pr[C^{\mathcal{O}}(1^\lambda) = x]$. To avoid circularity, queries are stratified by rank: a query of rank $r$ can only ask about samplers whose own oracle calls have rank strictly less than $r$.

Access Model (Coherent-Last): The security of the EFI pair is proven against distinguishers with coherent-last access. This model grants:

• Polynomial-length classical advice (or $O(\lambda)$ qubits of quantum advice).
• Polynomially many adaptive classical queries to the oracle.
• Exactly one coherent (superposition) query at the very end of the interaction.
• Polynomially many reference copies of the challenge states (generated by the public source).

3. Key Contributions and Results

A. Nonexistence of One-Way Puzzles (Theorem A(i))
Relative to $\mathcal{O}'$, OWPuzzs do not exist, even with a computationally unbounded verifier.

• Mechanism: The $Count$ oracle allows an adversary to estimate output probabilities of any sampler with exponential precision using polynomially many classical queries.
• Attack: The adversary can reconstruct the conditional distribution of keys given a puzzle bit-by-bit. By sampling from these estimated conditional probabilities, the adversary generates a key accepted by the verifier with probability $1 - \text{negl}(\lambda)$.
• Scope: This attack is purely classical and applies even if the adversary has full coherent access to the oracle (since the attack does not rely on quantum queries). Consequently, all primitives implied by OWPuzzs (multi-copy pseudorandom states, pure-output one-way state generators, quantum money) also do not exist relative to $\mathcal{O}'$.

B. Existence of EFI Pairs (Theorem A(ii))
Relative to $\mathcal{O}'$, the half-subspace pair $(\rho_0, \rho_1)$ forms a secure EFI pair against the defined access model.

• Classical Queries (Communication Complexity Reduction): The security against classical queries is reduced to the Vector-in-Subspace (VSP) problem. In VSP, Bob holds a subspace $H$, and Alice holds a vector promised to be in $H$ or $H^\perp$.
  • Quantum: VSP is easy (Alice sends the vector in $O(\log n)$ qubits; Bob measures).
  • Classical: VSP is hard, requiring $\Omega(n^{1/3})$ bits of communication (Klartag–Regev bound).
  • The author shows that any classical transcript of length $L$ about $H$ provides at most $O(L/n^{1/3})$ advantage in distinguishing the states. Since the adversary is limited to polynomially many classical bits, the advantage is negligible.
• Reference Copies: The adversary is granted reference copies of the states. The author shows these can be replaced by classical descriptions of the spans of the copies. Conditioning on these spans reduces the problem to a smaller VSP instance in the orthogonal complement, with only a negligible loss in security.
• Coherent Query (Matrix Concentration): The single coherent query allowed at the end of the interaction is bounded using tools from random matrix theory. The bias of a one-query adversary is shown to be $O(\sqrt{\log M / n})$, which is negligible for polynomial width $M$. Note: The EFI security claim is specifically restricted to this "coherent-last" model; the separation does not yet hold for adversaries with fully coherent access (multiple adaptive superposition queries) to the classical oracle.

C. Interactive Collapse (Theorem B)
Relative to $\mathcal{O}'$, there is no proof of quantumness for protocols with classical messages. Any quantum polynomial-time party in such a protocol can be simulated by a classical polynomial-time party making classical queries to $\mathcal{O}'$. This implies that quantum polynomial time offers no advantage over classical polynomial time for any task with classical inputs and outputs in this oracle world.

D. Separation of Primitives
The paper establishes a black-box barrier: no fully black-box construction of OWPuzzs from EFI pairs exists within the class of distinguishers defined by Model 1.1. This separates the "NanoCrypt" world (EFI pairs exist, OWPuzzs do not) from the "CountCrypt" world (OWPuzzs exist).

4. Significance and Limitations

Significance:

• Separation of Hardness: The work demonstrates that the hardness of distinguishing quantum states (EFI) does not necessarily imply the hardness of classical search problems (OWPuzzs). This suggests that the minimal assumption for quantum cryptography might be weaker than classical average-case hardness.
• New Proof Technique: The paper introduces a novel method for proving quantum state indistinguishability by reducing it to classical communication complexity lower bounds (specifically VSP).
• Oracle Construction: It provides a concrete single classical oracle that removes classical-output hardness (search, decision, and interaction) while preserving quantum state indistinguishability (under the coherent-last restriction).

Limitations and Open Questions:

• Coherent Access: The EFI security proof relies on the restriction to one coherent query at the end. The paper leaves open the question (Conjecture 8.2) whether the separation holds against adversaries with fully coherent access (multiple adaptive superposition queries) to the classical oracle.
• Advice: The security holds against $O(\lambda)$ qubits of quantum advice but does not rule out polynomial-size quantum advice combined with classical queries (which would effectively allow the adversary to synthesize arbitrary quantum side information before the classical transcript).
• Relativization: The results are oracle separations. They do not resolve whether OWPuzzs can be constructed from EFI pairs in the unrelativized world, nor do they imply $P \neq PSPACE$.

In summary, the paper constructs an oracle world where quantum cryptography can rest on the indistinguishability of quantum states (EFI pairs) without relying on the classical average-case hardness required for one-way puzzles, thereby clarifying the landscape of minimal assumptions in quantum cryptography.