Quantum Colloquium — Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier

Will cryptography survive quantum adversaries? Public-key cryptosystems based on post-quantum assumptions provide part of the answer. But what about the security of the many other cryptographic protocols and primitives? While some of these primitives directly inherit the post-quantum security of the underlying assumptions, many classical cryptosystems are proved secure by “rewinding” an interactive adversary to record its responses to multiple different challenges. Unfortunately, this technique is inapplicable if the adversary is running a quantum algorithm, since measuring the response can irreversibly disturb the adversary’s state.

In this talk, I will present a new quantum rewinding technique that enables recording the adversary's responses on any number of challenges. This opens the door to quantum security for many tasks. Our primary application here is to prove that Kilian’s four-message succinct argument system for NP is secure against quantum attack (assuming the post-quantum hardness of the Learning with Errors problem).

Joint work with Alessandro Chiesa, Nicholas Spooner, and Mark Zhandry. eprint.iacr.org/2021/334.pdf

Panel discussion: Zvika Brakerski (Weizmann Institute), Anne Broadbent (U. Ottawa), Yael Kalai (Microsoft Research), Umesh Vazirani (UC Berkeley; moderator)