One-Wayness in Quantum Cryptography

Understand

The existence of one-way functions is one of the most fundamental assumptions in classical cryptography.

• In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist.
• We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski, Canetti, and Qian recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations.
• However, their work focuses on decision-type primitives and does not cover search-type primitives like quantum money and digital signatures.