2025/03/06 by H. Y. Fu, Fu, Honghao, Kieran Mastel +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2503.04517
openalex publication_date 2025/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In their recent breakthrough result, Slofstra and the second author show that there is a two-player one-round perfect zero-knowledge MIP* protocol for RE (STOC'24). We build on their result to show that there exists a succinct two-player one-round perfect zero-knowledge MIP* protocol for RE against dishonest verifiers with polylog question size and O(1) answer size, or with O(1) question size and polylog answer size. To prove our result, we study the three central compression techniques underlying the MIP*=RE proof (Ji et al. '20): question reduction, oracularization, and answer reduction. We show that question reduction preserves the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against dishonest verifiers, and oracularization and answer reduction preserve the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against honest verifiers. Secondly, we show that every constraint-constraint binary constraint system (BCS) nonlocal game, which provides a quantum information characterization of MIP*, can be converted to a synchronous constraint-variable BCS game to preserve perfect completeness for our compression. Lastly, we present a parametrized perfect-zero-knowledge transformation of MIP* protocols, which generalizes the transformation in (Slofstra and Kieran STOC'24) . This transformation allows us to preserve the zero-knowledge property against dishonest verifiers in the recursively oracularized protocols in our compression.