| Summary: | Probabilistically Checkable Proofs (PCPs) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form “<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>∈</mo><mi mathvariant="script">L</mi></mrow></semantics></math></inline-formula>” by querying only a few proof bits. <i>Zero-Knowledge</i> 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 <i>honest</i> verifier makes 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 <i>single</i> 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 <i>leakage resilience</i>. 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.
|
|---|