Abstract

In the recent breakthrough result [MS24], Slofstra and Mastel show that there is a two-player one-round perfect zero-knowledge MIP∗ protocol for RE. We build on their result to show that there exists a succinct two-player one-round perfect zero-knowledge MIP∗ protocol for RE with polylog question size and O(1) answer size, or with O(1) question size and polylog answer size. To prove our result, we analyze the four central compression techniques underlying the MIP∗ = RE proof [JNV+20] — question reduction, oracularization, answer reduction, and parallel repetition — and show that they all preserve the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol. Furthermore, we complete the study of the conversion between constraint-constraint and constraint-variable binary constraint system (BCS) nonlocal games, which provide a quantum information characterization of MIP∗ protocols. While Paddock [Pad22] established that any near-perfect strategy for a constraint-variable game can be mapped to a constraint-constraint version, we prove the converse, fully establishing their equivalence.

Personal information

Xingjian Zhang (张行健) is a postdoctoral researcher in the Department of Computer Science at the University of Hong Kong. Before that, he obtained his PhD from IIIS, Tsinghua University, supervised by Prof. Xiongfeng Ma. Xingjian Zhang is interested in quantum nonlocality, quantum communication, and quantum cryptography.