Abstract
Recently, Zvika Brakerski proved an equivalence between the existence of quantum cryptography and the hardness of the black-hole radiation decoding problem of Harlow and Hayden. In this talk, I’ll give a new perspective on this equivalence, based on a reformulation of the radiation decoding problem as a distinguishing game. I’ll show that this distinguishing game precisely captures the security of a quantum commitment to one half of an EPR pair; this turns out to be necessary and sufficient for commitment-based quantum cryptography.
No prior knowledge of quantum commitments or black hole physics required. This talk will be mostly non-technical.
(Based on discussions with Sam Gunn and Alex Lombardi)