The Breakdown of Classical Minicrypt Equivalences in the Quantum-Computation Classical-Communication Model
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. As a separate result, we establish quantum sum-binding for the NOVY protocol, settling the question of its post-quantum security. We also generalize it to a fully black-box construction of a QCCC commitment from EV-OWPuzz with nearly uniform puzzle distribution, complementing our oracle separation results.
Related
- Normal-Field Evolution and the Breakdown of Classical Tearing in Current Sheets
- HTM: A Hybrid Classical-Quantum Computation Model
- Classical Algorithms for Function Computation in Gaussian Boson Sampling
- Towards exascale fully relativistic pseudopotential density functional theory calculations enabled by mixed-precision computation and compressed-communication using residual based subspace iteration
- QRecoupling.jl: numerical and exact computation of classical and quantum recoupling coefficients
BibTeX
@misc{chen2026breakdown,
title = {{The Breakdown of Classical Minicrypt Equivalences in the Quantum-Computation Classical-Communication Model}},
author = {Boyang Chen and Yiming Wang and Ziyi Xie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.33098},
eprint = {2609.33098},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33098},
}
RIS
TY - UNPB
TI - The Breakdown of Classical Minicrypt Equivalences in the Quantum-Computation Classical-Communication Model
AU - Boyang Chen
AU - Yiming Wang
AU - Ziyi Xie
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2609.33098
UR - https://arxiv.org/abs/2609.33098
AB - 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. As a separate result, we establish quantum sum-binding for the NOVY protocol, settling the question of its post-quantum security. We also generalize it to a fully black-box construction of a QCCC commitment from EV-OWPuzz with nearly uniform puzzle distribution, complementing our oracle separation results.
ER -