CountCrypt: Quantum Cryptography between QCMA and PP

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 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 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".