The notion of zero knowledge proofs underlies many of the mechanism for obtaining verifiable, privacy-preserving delegation of computation. Loosely speaking, zero knowledge proofs are interactive proof systems that reveal nothing other than the validity of the assertion being proven.
With the rise of quantum information and the growing evidence that small-to-medium scale quantum computers may be possible in the near future, we have ample reasons to understand what possibilities quantum computing offers for privacy-preserving delegation of computation, as well as what security threats does it pose.
In this talk, I will present the first construction of zero-knowledge proofs that are sound against quantum-entangled adversaries. The talk will be self-contained, and no preliminary knowledge in quantum computing is necessary.
Based on joint work with Alessandro Chiesa, Michael Forbes, and Nicholas Spooner (JACM 2021), as well as ongoing work.
Tom Gur is an associate professor in the Department of Computer Science at the University of Warwick, and a UKRI Future Leaders Fellow. He received his Ph.D. in 2017 from the Weizmann Institute of Science, under the supervision of Oded Goldreich, and spent two years at UC Berkeley before joining the University of Warwick. He was awarded the Shimon Even Prize in Theoretical Computer Science. His research interests are primarily in the foundations of computer science and combinatorics. Specific interests include sublinear-time algorithms, complexity theory, coding theory, cryptography, quantum computing, and more.