Abstract: In this talk I will discuss when we can “lift” classical reductions to post-quantum ones in a constructive manner. It is customary to argue that while this is problematic in the interactive setting, non-interactive reductions immediately carry over to the post-quantum setting. In this talk I will focus on the non-interactive setting and describe technical issues that arise, related to quantum auxiliary inputs. I will show how (and when) we can overcome these issues, and successfully lift a reduction to the post-quantum setting in a constructive manner. Specifically, I will show that any non-interactive non-adaptive reduction from problems with a polynomial solution space (such as decision problems) can be made post-quantum in a constructive manner. In contrast, I will show that for problems with super-polynomial solution space (such as general search problems) this cannot be done in general.
Bio: Yael Tauman Kalai is a Senior Principal Researcher at Microsoft Research and Adjunct Professor at the Massachusetts Institute of Technology (MIT). Kalai earned a B.Sc in Mathematics from the Hebrew University of Jerusalem, an MS in Computer Science and Applied Mathematics from The Weizmann Institute of Science, and a Ph.D. in Computer Science from MIT. Kalai’s honors include an Outstanding Master’s Thesis Prize (Weizmann Institute of Science, 2001), the George M. Sprowls Award for Best Doctoral Thesis in Computer Science (MIT, 2007). She is the recipient of the 2022 ACM Prize in Computing, and is a Fellow of the International Association for Cryptologic Research (IACR). Additionally, Kalai gave an Invited Talk at the International Congress of Mathematics (ICM, 2018).