2024/10/18 by Eli Goldin, Goldin, Eli, Tomoyuki Morimae +5 · 3 citations
Computer Science · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2410.14792
openalex publication_date 2024/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We construct a unitary oracle relative to which BQP=QCMA but quantum-computation-classical-communication (QCCC) commitments and QCCC multiparty non-interactive key exchange exist. We also construct a unitary oracle relative to which BQP=QMA, but quantum lightning (a stronger variant of quantum money) exists. This extends previous work by Kretschmer [Kretschmer, TQC22], which showed that there is a quantum oracle relative to which BQP=QMA but pseudorandm unitaries exist. We also show that (poly-round) QCCC key exchange, QCCC commitments, and two-round quantum key distribution can all be used to build one-way puzzles. One-way puzzles are a version of ``quantum samplable'' one-wayness and are an intermediate primitive between pseudorandom state generators and EFI pairs, the minimal quantum primitive. In particular, one-way puzzles cannot exist if BQP=PP. Our results together imply that aside from pseudorandom state generators, there is a large class of quantum cryptographic primitives which can exist even if BQP = QCMA, but are broken if BQP = PP. Furthermore, one-way puzzles are a minimal primitive for this class. We denote this class ``CountCrypt''.