On the Randomness Complexity of Interactive Proofs and Statistical Zero-Knowledge Proofs

Explore a 27-minute conference talk from the 2021 ITC Conference that delves into the randomness complexity of interactive proofs and statistical zero-knowledge proofs. Discover methods for reducing the number of random bits required by verifiers in interactive proofs and their application to statistical zero-knowledge proofs. Learn about the concept of randomness sparsification through the introduction of IP-PRG, its unconditional existence in non-uniform settings, and its existence under hardness assumptions in uniform settings. Examine the application of IP-PRG to SZK, the introduction of semi-malicious verifiers, and the resulting tradeoff between verifier randomness complexity and prover communication or simulation complexity. Gain insights into the canonical proof system for SD and its complete randomness sparsification. The talk covers key topics including problem statement, naive approach, genetic approach, nonuniformity, and statistical zero knowledge.