Paper 2015/1055
Making the Best of a Leaky Situation: ZeroKnowledge PCPs from LeakageResilient Circuits
Yuval Ishai, Mor Weiss, and 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 zeroknowledge 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 oraclebased 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 nonadaptively verifiable ZKPCPs, we suggest a new technique for compiling standard PCPs into ZKPCPs. Our approach is based on leakageresilient circuits, which are circuits that withstand certain ``sidechannel'' 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 sidechannel attack on the wirevalues of the circuit verifying membership in $L$, so a PCP constructed from a circuit resilient against such attacks would be ZK. However, a leakageresilient 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 wirevalues of the circuit on an \emph{illformed} ``encoded'' input, one can cause the verification to accept inputs $x\notin L$ \emph{with probability 1}. We overcome this obstacle by constructing leakageresilient circuits with the additional guarantee that illformed encoded inputs are detected. Using this approach, we obtain the following results: \begin{itemize} \sloppy \item We construct the first \emph{witnessindistinguishable} PCPs (WIPCP) for NP with nonadaptive verification. WIPCPs relax ZKPCPs by only requiring that different witnesses be indistinguishable. Our construction combines strong leakageresilient circuits as above with the PCP of Arora and Safra (FOCS '92), in which queries correspond to sidechannel 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 nonadaptively verifiable \emph{computational} ZKPCPs for NP in the common random string model, assuming that oneway functions exist. \item As an application of the above results, we construct \emph{3round} 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}
Metadata
 Available format(s)
 Publication info
 A major revision of an IACR publication in TCC 2016
 Keywords
 ZeroKnowledgeProbabilisticaly Checkable ProofsLeakageResilience
 Contact author(s)
 morw @ cs technion ac il
 History
 20151221: revised
 20151030: received
 See all versions
 Short URL
 https://ia.cr/2015/1055
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/1055, author = {Yuval Ishai and Mor Weiss and Guang Yang}, title = {Making the Best of a Leaky Situation: ZeroKnowledge {PCPs} from LeakageResilient Circuits}, howpublished = {Cryptology {ePrint} Archive, Paper 2015/1055}, year = {2015}, url = {https://eprint.iacr.org/2015/1055} }