All reports by Author Peter Hall:

__
TR24-156
| 7th October 2024
__

Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray, Peter Hall#### A Meta-Complexity Characterization of Quantum Cryptography

Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray, Peter Hall

We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a ... more >>>