Abstract
In the classical model of computation, one-way functions (OWF) are arguably minimal for computational cryptography, namely they are essential for almost any cryptographic application that can only be realized with respect to computationally bounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022); in particular, no minimal primitive is known.
We consider EFI pairs — efficiently samplable, statistically far and computationally indistinguishable pairs of quantum states. Building on the work of Yan (2022), which essentially shows equivalence between EFI pairs and statistical commitment schemes, we show that, in the quantum setting, EFI pairs are necessary for a large class of cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs for essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP 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.