Zero Knowledge Proofs in a Quantum World

The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally by making the physical assumption that spatially-isolated provers are playing independent strategies.  In this talk I will discuss new techniques involving coding theory, cryptography, complexity, and sublinear-time algorithms, that allow us to strengthen the foregoing result to hold even in light of quantum mechanics, which tells us that spatially-isolated provers can realise non-local correlated strategies by sharing a quantum entangled state. 

We provide the first construction of a zero-knowledge proof system that is sound against quantum entangled provers. Along the way, we introduce a framework that leverages local testability to ``lift’’ classical protocols to quantum protocols in a blackbox manner. The talk is directed towards a broad theoretical computer science audience, and in particular, no familiarity with quantum computing and cryptography is required.

The talk is based on a FOCS 2018 and QIP 2019 work, joint with Alessandro Chiesa, Michael Forbes, and Nick Spooner, as well as on forthcoming works.