EFI pairs — pairs of quantum states that are efficiently samplable, statistically far, yet computationally indistinguishable — are equivalent to quantum bit commitments and are necessary for a large class of quantum-cryptographic tasks, making them the leading candidate for the minimal primitive of quantum cryptography. Brakerski, Canetti, and Qian (ITCS 2023) asked what computational hardness the existence of EFI pairs requires and what it implies. Much of their question list is now resolved: weak EFI pairs amplify to full EFI pairs via an efficient quantum parallel repetition theorem; one-way state generators (hence quantum digital signatures and pure-state quantum money) imply EFI pairs; EFI pairs were constructed from well-studied #P-hardness and quantum-sampling conjectures that do not imply classical one-way functions; and oracle separations show EFI pairs do not yield efficiently verifiable one-way state generators or private-key quantum money. (1) Complexity barrier: does the existence of EFI pairs separate BQP from PSPACE — or can EFI pairs exist even when BQP = PSPACE; and is the best known sufficient condition (one-way puzzles, broken by P^#P machines, equivalent under sampling conjectures to P^#P not contained in infinitely-often BQP with polynomial quantum advice) tight for commitments, or could commitments rest on strictly weaker — even unconditional — hardness? (2) Do EFI pairs imply uniform pseudorandom states, closing the O(log λ)-advice gap in the known equivalence with non-uniform single-copy pseudorandom states? (3) Do quantum zero-knowledge arguments imply EFI pairs via instance-dependent commitments binding on NO instances?

Background

Classical computational cryptography rests on one-way functions (OWFs): functions that are easy to compute but hard to invert. OWFs are necessary and sufficient for almost every cryptographic task that is impossible against computationally unbounded adversaries. A convenient reformulation, due to Goldreich, is a pair of efficient classical samplers whose output distributions are statistically far (an unbounded distinguisher tells them apart with constant advantage) yet computationally indistinguishable (no efficient distinguisher gains more than a negligible advantage); such pairs exist if and only if OWFs exist. Quantum cryptography disrupts this picture. Kretschmer (TQC 2021) constructed a quantum oracle relative to which BQP = QMA yet pseudorandom quantum states exist, and proved that pseudorandom states cannot exist if BQP = PP; Kretschmer, Qian, Sinha, and Tal (STOC 2023) later built a classical oracle relative to which P = NP yet single-copy-secure pseudorandom states exist. (Here BQP is polynomial-time quantum computation, QMA its proof-checking analogue, PP probabilistic polynomial time with unbounded error, and PSPACE classical polynomial space.) So quantum cryptographic primitives can exist in worlds where classical cryptography does not, and the sub-OWF landscape is studied under the community nickname Microcrypt. Brakerski, Canetti, and Qian (BCQ; ITCS 2023) proposed the minimal primitive of this landscape: EFI pairs (efficient, far, indistinguishable) — a pair of efficient quantum circuit families sampling mixed states ρ0, ρ1 that are statistically far in trace distance (TD(ρ0, ρ1) ≥ 1/poly(λ), where λ is the security parameter) yet computationally indistinguishable to any quantum polynomial-time (QPT) distinguisher (distinguishing advantage negligible in λ). Building on Yan's equivalence between EFI pairs and quantum bit commitments — protocols where a committer locks a bit into a quantum state that must hide the bit from the receiver until opening (hiding) yet prevent the committer from changing it (binding) — BCQ showed EFI pairs are constructible from minimalistic versions of commitment schemes, oblivious transfer, and general secure multiparty computation, as well as from quantum computational zero-knowledge (QCZK) proofs for essentially any non-trivial language; conversely, any EFI pair yields QCZK proofs for all of QIP. Like OWFs classically, EFI pairs are thus simple, essential, and a linchpin for equivalence between primitives. Later work organized Microcrypt by the strongest classical oracle that breaks each primitive: primitives breakable by QCMA-type oracles; those breakable by PP or P^#P oracles (one-way puzzles, pseudorandom states — the CountCrypt layer); and those not known to be breakable by any classical oracle (EFI pairs, commitments — the NanoCrypt layer). Three neighboring primitives organize the known relations. Pseudorandom states (PRS) are efficiently computable state families indistinguishable from Haar-random (uniformly random) states even given polynomially many copies. One-way state generators (OWSGs), the quantum analogue of OWFs, efficiently generate a quantum state from a secret key such that no QPT algorithm can recover a compatible key from an honestly generated state; quantum digital signatures are equivalent to OWSGs, and private-key quantum money with pure banknote states implies OWSGs. One-way puzzles (OWPuzzs) are quantum samplers outputting a classical puzzle-key pair such that no QPT algorithm can find a valid key from the puzzle alone; OWPuzzs are broken by machines with P^#P power. Known relations: pure-state OWSGs imply commitments; statistically-verifiable OWSGs are equivalent to commitments; inefficiently-verifiable OWSGs are equivalent to EFI pairs; EFI pairs are equivalent to single-copy PRS with O(log λ) bits of non-uniform advice; and no black-box construction yields efficiently verifiable OWSGs (or private-key quantum money) from EFI pairs. The complexity-theoretic anchor of the open core is the unitary synthesis problem of Aaronson and Kuperberg (2007): can every n-qubit unitary U be implemented, even approximately, by a polynomial-size quantum circuit given oracle access to an arbitrary Boolean function f depending on U? Only lower bounds for one and 1.5 queries to f are known; the polynomial-query case is open. Its relevance to EFI: an unbounded distinguisher breaks any EFI pair by implementing the Helstrom measurement — the optimal two-outcome measurement for deciding between two known quantum states — and a PSPACE machine could do this if unitary synthesis (or just Helstrom-measurement synthesis) were solvable with a PSPACE oracle, since BQP with a PSPACE oracle is contained in PSPACE. Two more complexity notions figure in the questions: P^#P is P with an oracle for the counting class #P, and (io)BQP/qpoly is infinitely-often BQP with polynomial-length quantum advice. BCQ's discussion also asked whether quantum zero-knowledge arguments — interactive proofs with computational rather than statistical soundness — already force EFI pairs; the natural route yields instance-dependent commitments that are statistically hiding on YES instances but only computationally binding on NO instances, and whether that suffices (perhaps after amplification) was left open.

Problem Statement

The problem is the surviving open core of the open questions of Brakerski, Canetti, and Qian (ITCS 2023): locate the existence of EFI pairs — efficiently samplable, statistically far, computationally indistinguishable pairs of mixed quantum states, equivalent to quantum bit commitments — on the computational-complexity map, by determining what hardness their existence entails, what hardness suffices for them, and which weaker protocol notions already force them. Concretely, the following three questions are open; the problem is fully resolved when all three are settled, and each question is independently a complete resolution of its facet. (Q1) Complexity barrier and separation. Does the existence of EFI pairs separate BQP from PSPACE — or can EFI pairs exist even when BQP = PSPACE? In the words of the source paper: 'is P vs PSPACE a (classical) barrier for the existence of EFI pairs?' Within the same question: the strongest known sufficient condition is the existence of one-way puzzles — equivalent, under any sampling-based quantum-advantage conjecture, to P^#P not contained in (io)BQP/qpoly — and this bound is tight for one-way puzzles, which are broken by P^#P machines; determine whether it is tight for commitments, or whether EFI pairs can be based on strictly weaker assumptions, down to and including unconditional existence. (Q2) Quantum pseudorandomness from EFI. Do EFI pairs imply uniform pseudorandom states? It is known that EFI pairs are equivalent to single-copy-secure PRS generators with O(log λ) bits of non-uniform advice, and that single-copy PRS generically amplify to k-copy PRS; the open question is whether the advice can be removed, i.e., whether EFI pairs imply uniform single-copy PRS (hence standard multi-copy PRS) — the quantum analogue of the classical equivalence between Goldreich's statistically-far computationally-indistinguishable distribution pairs and pseudorandom generators. (Q3) Arguments imply EFI. Does the existence of quantum computational zero-knowledge arguments (interactive proofs with computational soundness) for any non-trivial language imply the existence of EFI pairs? The natural route produces instance-dependent commitments that are statistically hiding yet only computationally binding on NO instances; the source paper asked whether such commitments — perhaps after hardness amplification, which is now available via the efficient quantum parallel repetition theorem — can be converted into EFI pairs. No implication or refutation is known.

References

  1. Zvika Brakerski, Ran Canetti, Luowen Qian. On the Computational Hardness Needed for Quantum Cryptography. Innovations in Theoretical Computer Science (ITCS 2023), LIPIcs vol. 251, pages 24:1-24:21, DOI 10.4230/LIPIcs.ITCS.2023.24; arXiv:2209.04101. https://doi.org/10.4230/LIPIcs.ITCS.2023.24
  2. John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen. An Efficient Quantum Parallel Repetition Theorem and Applications. STOC 2024; arXiv:2311.10681. https://arxiv.org/abs/2311.10681
  3. Dakshita Khurana, Kabir Tomer. Commitments from Quantum One-Wayness. STOC 2024; arXiv:2310.11526. https://arxiv.org/abs/2310.11526
  4. Rishabh Batra, Rahul Jain. Commitments are Equivalent to Statistically-Verifiable One-Way State Generators. FOCS 2024, pages 1178-1192; arXiv:2404.03220. https://arxiv.org/abs/2404.03220
  5. Dakshita Khurana, Kabir Tomer. Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P-Hardness. STOC 2025; arXiv:2409.15248. https://arxiv.org/abs/2409.15248
  6. John Bostanci, Boyang Chen, Barak Nehoran. Oracle Separation Between Quantum Commitments and Quantum One-Wayness. EUROCRYPT 2025, LNCS 15607, pages 3-22; arXiv:2410.03358. https://arxiv.org/abs/2410.03358
  7. Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, Takashi Yamakawa. A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID. arXiv:2410.03453. https://arxiv.org/abs/2410.03453
  8. Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, Xingjian Li. A Meta-Complexity Characterization of Minimal Quantum Cryptography. STOC 2026, pages 675-686; arXiv:2510.07859. https://arxiv.org/abs/2510.07859
  9. Zvika Brakerski, Miri Zenilman. Generic Number-of-Copies Amplification for Pseudorandom States. arXiv:2606.29325. https://arxiv.org/abs/2606.29325
  10. Alex Lombardi, Fermi Ma, John Wright. A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography. STOC 2024; arXiv:2310.08870. https://arxiv.org/abs/2310.08870
  11. William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal. Quantum Cryptography in Algorithmica. STOC 2023; arXiv:2212.00879. https://arxiv.org/abs/2212.00879
  12. Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, Takashi Yamakawa. CountCrypt: Quantum Cryptography between QCMA and PP. arXiv:2410.14792. https://arxiv.org/abs/2410.14792
  13. Giulio Malavolta, Tomoyuki Morimae, Michael Walter, Takashi Yamakawa. Exponential Quantum One-Wayness and EFI Pairs. arXiv:2404.13699. https://arxiv.org/abs/2404.13699
  14. Tomoyuki Morimae, Takashi Yamakawa. One-Wayness in Quantum Cryptography. arXiv:2210.03394. https://arxiv.org/abs/2210.03394
  15. Tomoyuki Morimae, Takashi Yamakawa. Quantum Commitments and Signatures Without One-Way Functions. CRYPTO 2022; arXiv:2112.06369. https://arxiv.org/abs/2112.06369
  16. Prabhanjan Ananth, Luowen Qian, Henry Yuen. Cryptography from Pseudorandom Quantum States. arXiv:2112.10020. https://arxiv.org/abs/2112.10020
  17. Zhengfeng Ji, Yi-Kai Liu, Fang Song. Pseudorandom Quantum States. CRYPTO 2018 (Advances in Cryptology - CRYPTO 2018, Part III, LNCS 10993, pages 126-152), DOI 10.1007/978-3-319-96878-0_5; arXiv:1711.00385 (preprint title: Pseudorandom States, Non-Cloning Theorems and Quantum Money). https://arxiv.org/abs/1711.00385
  18. William Kretschmer. Quantum Pseudorandomness and Classical Complexity. TQC 2021, DOI 10.4230/LIPIcs.TQC.2021.2; arXiv:2103.09320. https://arxiv.org/abs/2103.09320
  19. Scott Aaronson, Greg Kuperberg. Quantum Versus Classical Proofs and Advice. Theory of Computing, Volume 3, Article 7, pages 129-157, 2007, DOI 10.4086/toc.2007.v003a007. https://doi.org/10.4086/toc.2007.v003a007
  20. Jun Yan. General Properties of Quantum Bit Commitments. Cryptology ePrint Archive, Report 2020/1488. https://eprint.iacr.org/2020/1488
  21. Oded Goldreich. A Note on Computational Indistinguishability. Information Processing Letters 34(6):277-281, 1990, DOI 10.1016/0020-0190(90)90010-U. https://doi.org/10.1016/0020-0190(90)90010-U
  22. Fangqi Dong, Alex Lombardi, Fermi Ma. Explicit Separations for One-Query Unitary Synthesis. arXiv:2607.26478. https://arxiv.org/abs/2607.26478
  23. Eric Huang. A 1.5-Query Lower Bound for the Unitary Synthesis Problem. arXiv:2508.13215. https://arxiv.org/abs/2508.13215
  24. Zvika Brakerski, Henry Yuen. On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem. arXiv:2605.09957. https://arxiv.org/abs/2605.09957
  25. Taiga Hiroka, Tomoyuki Morimae. Quantum Cryptography and Meta-Complexity. CRYPTO 2025; arXiv:2410.01369. https://arxiv.org/abs/2410.01369
  26. Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray, Peter Hall. A Meta-Complexity Characterization of Quantum Cryptography. EUROCRYPT 2025, LNCS 15607, pages 82-107; arXiv:2410.04984. https://arxiv.org/abs/2410.04984