A Meta-Complexity Characterization of Minimal Quantum Cryptography

We give a meta-complexity characterization of EFI pairs, which are considered the "minimal" primitive in quantum cryptography and are equivalent to quantum commitments. More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable...