Welcome to the resource topic for 2012/229
Title:
Languages with Efficient Zero-Knowledge PCP’s are in SZK
Authors: Mohammad Mahmoody, 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.
ePrint: https://eprint.iacr.org/2012/229
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .