Paper 2022/1181

On the computational hardness needed for quantum cryptography

Zvika Brakerski, Weizmann Institute of Science
Ran Canetti, Boston University
Luowen Qian, Boston University

In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs — efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from 𝖰𝖢𝖹𝖪 proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (𝖰𝖢𝖹𝖪) proofs for all of 𝖰𝖨𝖯 from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.

Available format(s)
Publication info
Published elsewhere. ITCS 2023
quantum cryptography efi commitment scheme oblivious transfer zero knowledge secure multiparty computation
Contact author(s)
zvika brakerski @ weizmann ac il
canetti @ bu edu
luowenq @ bu edu
2022-11-24: revised
2022-09-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zvika Brakerski and Ran Canetti and Luowen Qian},
      title = {On the computational hardness needed for quantum cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1181},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.