IACR News item: 30 October 2015
Yuval Ishai; Mor Weiss; Guang Yang
ePrint ReportOriginating 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}
Additional news items may be found on the IACR news page.