CryptoDB
Quantum Cryptography and Meta-Complexity
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | In classical cryptography, one-way functions (OWFs) and pseudorandom generators (PRGs) are the minimal assumption. On the other hand, in quantum cryptography, several quantum analogues of OWFs and PRGs have been introduced, and shown to be potentially weaker than OWFs and PRGs. These analogues still imply many useful applications such as private-key quantum money schemes, secret-key encryption, message authentication codes, digital signatures, commitments, and multiparty computations. Now that the possibility of quantum cryptography without OWFs has opened up, the most important goal in the field is to build a foundation of it. In this paper, we, for the first time, characterize quantum cryptographic primitives with meta-complexity. We show that one-way puzzles (OWPuzzs), which are a quantum analogue of OWFs, exist if and only if GapK is weakly-quantum-average-hard. GapK is a promise problem to decide whether a given bit string has a small Kolmogorov complexity or not. Weakly-quantum-average-hard means that an instance is sampled from a QPT samplable distribution, and for any QPT adversary the probability that it makes mistake is larger than ${\rm 1/poly}$. We also show that if a quantum analogue of PRGs, quantum PRGs, exist then GapK is strongly-quantum-average-hard. Here, strongly-quantum-average-hard is a stronger version of weakly-quantum-average-hard where the probability that the adversary makes mistake is larger than $1/2-1/{\rm poly}$ for any ${\rm poly}$. Finally, we show that if GapK is weakly-classical-average-hard, then inefficient-verifier proofs of quantumness (IV-PoQ) exist. Weakly-classical-average-hard is the same as weakly-quantum-average-hard except that the adversary is PPT. IV-PoQ are a generalization of proofs of quantumness (PoQ) that capture sampling-based and search-based quantum advantage, and an important application of OWPuzzs. This is the fist time that quantum advantage is based on meta-complexity. |
BibTeX
@inproceedings{crypto-2025-35620,
title={Quantum Cryptography and Meta-Complexity},
publisher={Springer-Verlag},
author={Taiga Hiroka and Tomoyuki Morimae},
year=2025
}