Paper 2022/1524

Shielding Probabilistically Checkable Proofs: Zero-Knowledge PCPs from Leakage Resilience

Abstract

Probabilistically Checkable Proofs (PCPs) allow a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form ``$x\in\mathcal{L}$'' by querying only few proof bits. Zero-Knowledge PCPs (ZK-PCPs) enhance standard PCPs to additionally guarantee that the view of any (possibly malicious) verifier querying a bounded number of proof bits can be efficiently simulated up to a small statistical distance. The first ZK-PCP construction of Kilian, Petrank and Tardos (STOC 1997), and following constructions employing similar techniques, necessitate that the honest verifier make several rounds of queries to the proof. This undesirable property, which is inherent to their technique, translates into increased round complexity in cryptographic applications of ZK-PCPs. We survey two recent ZK-PCP constructions -- due to Ishai, Yang and Weiss (TCC 2016-A), and Hazay, Venkitasubramaniam, and Weiss (ITC 2021) -- in which the honest verifier makes a single round of queries to the proof. Both constructions use entirely different techniques compared to previous ZK-PCP constructions, by showing connections to the seemingly-unrelated notion of leakage resilience. These constructions are incomparable to previous ZK-PCP constructions: while on the one hand the honest verifier only makes a single round of queries to the proof, these ZK-PCPs either obtain a smaller (polynomial) ratio between the query complexity of the honest and malicious verifiers, or obtain a weaker ZK guarantee in which the ZK simulator is not necessarily efficient.