Abstract
Will cryptography survive quantum adversaries? Basic primitives such as encryption based on post-quantum computational assumptions provide part of the answer. But what about the security of cryptosystems that *use* these building blocks? While some directly inherit the post-quantum security of the underlying assumptions, many classical protocols are proved secure by “rewinding” an interactive adversary and using its responses on multiple different challenges. Unfortunately, this classical technique is inapplicable if the adversary is running a quantum algorithm, since measuring the response can irreversibly disturb the adversary’s state. This leaves the post-quantum security of many cryptographic protocols poorly understood.
In this tutorial, we will develop the techniques, tools, and abstractions necessary to translate classical rewinding proofs to the post-quantum setting. Our primary goal will be to prove post-quantum soundness and zero-knowledge for decades-old protocols such as Blum’s Hamiltonicity protocol, Kilian’s succinct arguments for NP, and the Graph Isomorphism + Non-Isomorphism protocols of Goldreich, Micali, and Wigderson.