arXiv preprint ·
The Breakdown of Classical Minicrypt Equivalences in the Quantum-Computation Classical-Communication Model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Classically, it is well-known that several fundamental cryptographic primitives, including one-way functions, pseudorandom number generators, commitments, and signatures, characterize the same cryptographic world, which is known as "Minicrypt". In this paper, we investigate to what extent this picture persists in the quantum-computation classical-communication (QCCC) setting, where parties may perform quantum local computation, but communicate through only classical messages. We demonstrate that the classical Minicrypt landscape breaks down in the QCCC model by oracle separations. We construct two oracle worlds where efficiently verifiable one-way puzzles (EV-OWPuzz) exist. By a known equivalence, QCCC one-time signatures also exist in both worlds. In the first, one-way functions do not exist, even if we allow quantum pseudodeterministic evaluation. In the second, QCCC bit commitments do not exist. Thus, the classical Minicrypt reductions from signatures to one-way functions and bit commitments have no fully black-box counterparts in the QCCC setting. Our proofs develop techniques for analyzing the random phase states, including a concentration theorem and an LOCC decoupling theorem, which may be of independent interest.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Loss-Resilient Quantum Networking with Dicke Entanglement
Native implementation of the machine-learned Skala exchange-correlation functional in CP2K: Unified one-centre reconstruction for molecular and condensed-phase calculations
Tensor-Engineered Van der Waals NbOCl2 Resonant Metasurface for Polarization-entangled Bell State Generation
Quantum Monte Carlo Tree Search with Fixed Confidence
The equivalence of topological indices for $\mathrm{U}(1)\rtimes\mathbb{Z}_2$-symmetric quantum spin chains
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.