Oracle Separation Between Quantum Commitments and Quantum One-Wayness

We show that there exists an oracle relative to which quantum commitments exist but no (efficiently verifiable) one-way state generators exist. Both have been widely considered candidates for replacing oneway functions as the minimal assumption for cryptography-the weakest cryptographic assumption implied by all of computational cryptography. Recent work has shown that commitments can be constructed from one-way state generators, but the other direction has remained open. Our results rule out any black-box construction, and thus settles this crucial open problem, suggesting that quantum commitments (as well as its equivalency class of EFI pairs, quantum oblivious transfer, and secure quantum multiparty computation) appear to be strictly weakest among all known cryptographic primitives.

Note: There is a bug in Section 5, pointed out to us by Eli Goldin and Mark Zhandry. While Lemma 5.5 is true, it only holds for fixed states 𝜌, and thus can not be applied to get an oracle separation between 𝖤𝖥𝖨 pairs and 𝖮𝖶𝖲𝖦 in the Haar random swap model. The construction of 𝖮𝖶𝖯𝗎𝗓𝗓 and 𝖤𝖥𝖨 can be lifted to the unitary model but the attack on 𝖮𝖶𝖲𝖦 cannot be lifted with the approach in this paper. Treating the swap oracle as a reflection around |0⟩ -|𝜓⟩ for a Haar random |𝜓⟩ allows one recover the result, see [16] for a more detailed discussion. We leave the buggy attack on 𝖮𝖶𝖲𝖦 in that section of the paper in the arXiv version of this paper for future reference.