Crypto Seminar - Eli Goldin November 14, 2024 4:30pm — 5:30pm Location: In Person and Virtual - ET - Blelloch-Skees Conference Room, Gates Hillman 8115 and Zoom Speaker: ELI GOLDIN, Ph.D. Student, Department of Computer Science, New York University https://eligoldin.com/ CountCrypt: Quantum Cryptography between QCMA and PP We construct a quantum oracle relative to which BQP = 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 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 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 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".In Person and Zoom Participation. See announcement. Event Website: https://sites.google.com/view/crypto-seminar/home Add event to Google Add event to iCal
