Oracle Separation Between Quantum Commitments and Quantum One-wayness

John Bostanci; Boyang Chen; Barak Nehoran

Paper 2024/1568

Oracle Separation Between Quantum Commitments and Quantum One-wayness

John Bostanci

, Columbia University

Boyang Chen, Tsinghua University

Barak Nehoran

, Princeton University

Abstract

We show that there exists a unitary quantum oracle relative to which quantum commitments exist but no (efficiently verifiable) one-way state generators exist. Both have been widely considered candidates for replacing one-way 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 settle 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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: quantum minimal assumptions
Contact author(s): johnb @ cs columbia edu
by-chen24 @ mails tsinghua edu cn
bnehoran @ princeton edu
History: 2024-10-05: last of 2 revisions; 2024-10-04: received; See all versions
Short URL: https://ia.cr/2024/1568
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1568,
      author = {John Bostanci and Boyang Chen and Barak Nehoran},
      title = {Oracle Separation Between Quantum Commitments and Quantum One-wayness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1568},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1568}
}