CountCrypt: Quantum Cryptography between QCMA and PP

Eli Goldin; Tomoyuki Morimae; Saachi Mutreja; Takashi Yamakawa

Paper 2024/1707

CountCrypt: Quantum Cryptography between QCMA and PP

Eli Goldin

, New York University

Tomoyuki Morimae, Kyoto University

Saachi Mutreja

, Columbia University

Takashi Yamakawa

, NTT (Japan)

Abstract

We construct a quantum oracle relative to which $\mathbf{BQP}=\mathbf{QCMA}$ but quantum-computation-classical-communication (QCCC) key exchange, QCCC commitments, and two-round quantum key distribution exist. We also construct an oracle relative to which $\mathbf{BQP}=\mathbf{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 $\mathbf{BQP}=\mathbf{QMA}$ but pseudorandom state generators (a quantum variant of pseudorandom generators) exist. We also show that 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 $\mathbf{BQP}=\mathbf{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 $\mathbf{BQP} = \mathbf{QCMA}$, but are broken if $\mathbf{BQP} = \mathbf{PP}$. Furthermore, one-way puzzles are a minimal primitive for this class. We denote this class "CountCrypt".

Note: Updated bibliography

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: quantum cryptography minimal assumptions black-box separation CountCrypt MicroCrypt QCCC
Contact author(s): eli goldin @ nyu edu
tomoyuki morimae @ yukawa kyoto-u ac jp
saachi @ berkeley edu
takashi yamakawa @ ntt com
History: 2024-10-24: revised; 2024-10-18: received; See all versions
Short URL: https://ia.cr/2024/1707
License: CC BY-SA

BibTeX

@misc{cryptoeprint:2024/1707,
      author = {Eli Goldin and Tomoyuki Morimae and Saachi Mutreja and Takashi Yamakawa},
      title = {{CountCrypt}: Quantum Cryptography between {QCMA} and {PP}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1707},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1707}
}