On Central Primitives for Quantum Cryptography with Classical Communication

Recent work has introduced the “Quantum-Computation Classical-Communication” (QCCC) (Chung et al.) setting for cryptography. There has been some evidence that One Way Puzzles ( \(\textsf{OWPuzz}\) ) are the natural central cryptographic primitive for this setting (Khurana and Tomer). For a primitive to be considered central it should have several characteristics. It should be well behaved (which for this paper we will think of as having amplification, combiners, and universal constructions); it should be implied by a wide variety of other primitives; and it should be equivalent to some class of useful primitives. We present combiners, correctness and security amplification, and a universal construction for \(\textsf{OWPuzz}\) . Our proof of security amplification uses a new and cleaner construction of EFI from \(\textsf{OWPuzz}\) (in comparison to the result of Khurana and Tomer) that generalizes to weak \(\textsf{OWPuzz}\) and is the most technically involved section of the paper. It was previously known that \(\textsf{OWPuzz}\) are implied by other primitives of interest including commitments, symmetric key encryption, one way state generators ( \(\textsf{OWSG}\) ), and therefore pseudorandom states ( \(\textsf{PRS}\) ). However we are able to rule out \(\textsf{OWPuzz}\) ’s equivalence to many of these primitives by showing a black box separation between general \(\textsf{OWPuzz}\) and a restricted class of \(\textsf{OWPuzz}\) (those with efficient verification, which we call \(\mathsf {EV-OWPuzz}\) ). We then show that \(\mathsf {EV-OWPuzz}\) are also implied by most of these primitives, which separates them from \(\textsf{OWPuzz}\) as well. This separation also separates extending \(\textsf{PRS}\) from highly compressing \(\textsf{PRS}\) answering an open question of Ananth et al.