Dr. Alex Lombardi, Simons-Berkeley
15:00 p.m., August 4, 2023, GMT+8
Jingyuan Campus No.5 Courtyard Room 204
We show a general method of compiling any k-prover non-local game into a single-prover interactive game maintaining the same (quantum) completeness and (classical) soundness guarantees. Our compiler uses a quantum homomorphic encryption scheme as a cryptographic mechanism to (provably) simulate the effect of spatial separation. In conjunction with the rich literature on (entangled) multi-prover non-local games, our compiler gives a broad framework for constructing mechanisms to classically verify quantum advantage. Some follow-up work analyzing quantum soundness of some such protocols will also be discussed.
The talk is mainly based on joint work with Yael Kalai, Vinod Vaikuntanathan, and Lisa Yang (https://eprint.iacr.org/2022/400).
Alex Lombardi is a Simons-Berkeley postdoctoral fellow hosted by Shafi Goldwasser. His current interests lie mainly in the theory and foundations of cryptography. He was a graduate student at MIT, advised by Vinod Vaikuntanathan. In the coming fall, Alex will join Princeton as an Assistant Professor of Computer Science.
Center on Frontiers of Computing Studies