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.
The first lecture will serve as a gentle introduction to the tools, techniques, and abstractions necessary to prove classical cryptosystems secure against quantum attacks. Topics include: commitment schemes secure against quantum attacks, proving soundness using Unruh's rewinding technique, and proving zero-knowledge using Watrous' rewinding technique.
Copyright. All Rights Reserved.