Cryptology City

[CCGH25] A Meta-Complexity Characterization of Quantum Cryptography

Authors: Bruno P. Cavalar, Eli Goldin, Matthew Gray, Peter Hall | Venue: Eurocrypt 2025 | Source

Abstract

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 uncomputable problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of a meta-complexity problem, initiated by Liu and Pass. Moreover, since the average-case hardness of Kolmogorov complexity over classically polynomial-time samplable distributions characterizes one-way functions, this result poses one-way puzzles as a natural generalization of one-way functions to the quantum setting. Furthermore, our equivalence goes through probability estimation, giving us the additional equivalence that one-way puzzles exist if and only if there is a quantum samplable distribution over which probability estimation is hard. We also observe that the oracle worlds of defined by Kretschmer et. al. rule out any relativizing characterization of one-way puzzles by the hardness of a problem in or , which means that it may not be possible with current techniques to characterize one-way puzzles with another meta-complexity problem.

BibTeX

@Inproceedings{EC:CGGH25,
  author = {Bruno Pasqualotto Cavalar and Eli Goldin and Matthew Gray and Peter Hall},
  title = {A Meta-complexity Characterization of Quantum Cryptography},
  pages = {82--107},
  editor = {Serge Fehr and Pierre-Alain Fouque},
  booktitle = {Advances in Cryptology -- {EUROCRYPT}~2025, Part~VII},
  volume = {15607},
  series = {Lecture Notes in Computer Science},
  address = {Madrid, Spain},
  month = {may~4--8},
  publisher = {Springer, Cham, Switzerland},
  year = {2025},
  doi = {10.1007/978-3-031-91098-2_4},
}

Graph View