Welcome to the resource topic for 2024/356
Title:
On Central Primitives for Quantum Cryptography with Classical Communication
Authors: Kai-Min Chung, Eli Goldin, Matthew Gray
Abstract: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 (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 amplifica-
tion, and a universal construction for OWPuzz. Our proof of security amplification
uses a new and cleaner version construction of EFI from OWPuzz (in comparison to
the result of Khurana and Tomer) that generalizes to weak OWPuzz and is the most
technically involved section of the paper. It was previously known that OWPuzz are
implied by other primitives of interest including commitments, symmetric key encryp-
tion, one way state generators (OWSG), and therefore pseudorandom states (PRS).
However we are able to rule out OWPuzz’s equivalence to many of these primitives
by showing a black box separation between general OWPuzz and a restricted class
of OWPuzz (those with efficient verification, which we call EV − OWPuzz). We then
show that EV − OWPuzz are also implied by most of these primitives, which separates
them from OWPuzz as well. This separation also separates extending PRS from highly
compressing PRS answering an open question of Ananth et. al.
ePrint: https://eprint.iacr.org/2024/356
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 .