Paper 2024/1707
CountCrypt: Quantum Cryptography between QCMA and PP
, New York University, Columbia University, NTT (Japan)Abstract
We construct a unitary oracle relative to which $\mathbf{BQP}=\mathbf{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 $\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 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 $\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: Upgraded CPTP separations to unitary separations
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. arxiv
- Keywords
- quantum cryptographyminimal assumptionsblack-box separationCountCryptMicroCryptQCCC
- Contact author(s)
-
eli goldin @ nyu edu
tomoyuki morimae @ yukawa kyoto-u ac jp
saachi @ berkeley edu
takashi yamakawa @ ntt com - History
- 2025-10-06: last of 2 revisions
- 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}
}
