Welcome to the resource topic for
**2024/1707**

**Title:**

CountCrypt: Quantum Cryptography between QCMA and PP

**Authors:**
Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, Takashi Yamakawa

**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”.

**ePrint:**
https://eprint.iacr.org/2024/1707

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .