**Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits**

*Yuval Ishai; Mor Weiss; Guang Yang*

**Abstract: **A Probabilistically Checkable Proof (PCP) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form ``$x\in L$'' by querying only few bits of the proof. A zero-knowledge PCP (ZKPCP) is a PCP with the additional guarantee that the view of any verifier querying a bounded number of proof bits can be efficiently simulated given the input $x$ alone, where the simulated and actual views are statistically close.

Originating from the first ZKPCP construction of Kilian et~al.(STOC~'97), all previous constructions relied on locking schemes, an unconditionally secure oracle-based commitment primitive. The use of locking schemes makes the verifier \emph{inherently} adaptive, namely, it needs to make at least two rounds of queries to the proof.

Motivated by the goal of constructing non-adaptively verifiable ZKPCPs, we suggest a new technique for compiling standard PCPs into ZKPCPs. Our approach is based on leakage-resilient circuits, which are circuits that withstand certain ``side-channel'' attacks, in the sense that these attacks reveal nothing about the (properly encoded) input, other than the output. We observe that the verifier's oracle queries constitute a side-channel attack on the wire-values of the circuit verifying membership in $L$, so a PCP constructed from a circuit resilient against such attacks would be ZK. However, a leakage-resilient circuit evaluates the desired function \emph{only if} its input is properly encoded, i.e., has a specific structure, whereas by generating a ``proof'' from the wire-values of the circuit on an \emph{ill-formed} ``encoded'' input, one can cause the verification to accept inputs $x\notin L$ \emph{with probability 1}. We overcome this obstacle by constructing leakage-resilient circuits with the additional guarantee that ill-formed encoded inputs are detected. Using this approach, we obtain the following results: \begin{itemize} \sloppy \item We construct the first \emph{witness-indistinguishable} PCPs (WIPCP) for NP with non-adaptive verification. WIPCPs relax ZKPCPs by only requiring that different witnesses be indistinguishable. Our construction combines strong leakage-resilient circuits as above with the PCP of Arora and Safra (FOCS '92), in which queries correspond to side-channel attacks by shallow circuits, and with correlation bounds for shallow circuits due to Lovett and Srivinasan (RANDOM '11). \item Building on these WIPCPs, we construct non-adaptively verifiable \emph{computational} ZKPCPs for NP in the common random string model, assuming that one-way functions exist. \item As an application of the above results, we construct \emph{3-round} WI and ZK proofs for NP in a distributed setting in which the prover and the verifier interact with multiple servers of which $t$ can be corrupted, and the total communication involving the verifier consists of $\poly\log\left(t\right)$ bits. \end{itemize}

**Category / Keywords: **Zero-Knowledge, Probabilisticaly Checkable Proofs, Leakage-Resilience

**Original Publication**** (with major differences): **IACR-TCC-2016

**Date: **received 30 Oct 2015, last revised 21 Dec 2015

**Contact author: **morw at cs technion ac il

**Available format(s): **PDF | BibTeX Citation

**Version: **20151221:075235 (All versions of this report)

**Short URL: **ia.cr/2015/1055

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]