CryptoDB
Hard Quantum Extrapolations in Quantum Cryptography
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | Although one-way functions are well-established as the minimal primitive for classical cryptography, a minimal primitive for quantum cryptography is still unclear. Universal extrapolation, first considered by Impagliazzo and Levin (1990), is hard if and only if one-way functions exist. Towards better understanding minimal assumptions for quantum cryptography, we study the quantum analogues of the universal extrapolation task. Specifically, we put forth the classical→quantum extrapolation task, where we ask to extrapolate the rest of a bipartite pure state given the first register measured in the computational basis. We then use it as a key component to establish new connections in quantum cryptography: (a) quantum commitments exist if classical→quantum extrapolation is hard; and (b) classical→quantum extrapolation is hard if any of the following cryptographic primitives exists: quantum public-key cryptography (such as quantum money and signatures) with a classical public key or 2-message quantum key distribution protocols. For future work, we further generalize the extrapolation task and propose a fully quantum analogue. We show that it is hard if quantum commitments exist, and it is easy for quantum polynomial space. |
BibTeX
@inproceedings{eurocrypt-2025-35038,
title={Hard Quantum Extrapolations in Quantum Cryptography},
publisher={Springer-Verlag},
author={Luowen Qian and Justin Raizes and Mark Zhandry},
year=2025
}