Paper 2012/229

Languages with Efficient Zero-Knowledge PCP's are in SZK

Mohammad Mahmoody and David Xiao

Abstract

A \emph{Zero-Knowledge PCP} (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $\NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, revisited the possibility of \emph{efficient} ZK-PCPs for all $L \in \NP$ where the PCP is encoded as a polynomial-size circuit that given a query $i$ returns the $i\th$ symbol of the PCP. Ishai \etal showed that there is no efficient ZK-PCP for $\NP$ with a \emph{non-adaptive} verifier, who prepares all of its PCP queries before seeing any answers, unless $\NP \se \coAM$ and polynomial-time hierarchy collapses. The question of whether \emph{adaptive} verification can lead to efficient ZK-PCPs for $\NP$ remained open. In this work, we resolve this question and show that any language or promise problem with efficient ZK-PCPs must be in $\SZK$ (the class of promise problems with a statistical zero-knowledge \emph{single prover} proof system). Therefore, no $\NP$-complete problem can have an efficient ZK-PCP unless $\NP \se \SZK$ (which also implies $\NP \se \coAM$ and the polynomial-time hierarchy collapses). We prove our result by reducing any promise problem with an efficient ZK-PCP to two instances of the $\CEA$ problem defined and studied by Vadhan (FOCS'04) which is known to be complete for the class $\SZK$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
zero knowledgepcpszk
Contact author(s)
david xiao @ gmail com
History
2012-04-30: received
Short URL
https://ia.cr/2012/229
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/229,
      author = {Mohammad Mahmoody and David Xiao},
      title = {Languages with Efficient Zero-Knowledge PCP's are in SZK},
      howpublished = {Cryptology ePrint Archive, Paper 2012/229},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/229}},
      url = {https://eprint.iacr.org/2012/229}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.