DIMACS TR: 97-27

Probabilistically Checkable Proofs with Zero Knowledge

Authors: Joe Kilian, Erez Petrank and Gábor Tardos


We construct PCPs with strong zero-knowledge properties. First, we construct polynomially bounded (in size) PCP's for {\sf NP} which can be checked using poly-logarithmic queries, with polynomially low error, yet are statistical zero-knowledge against an adversary that makes $U$ arbitrary queries, where $U$ can be set to any polynomial. Second, we construct PCPs for {\sf{NEXPTIME}} that can be checked using polynomially many queries, yet are statistically zero-knowledge against any polynomially bounded adversary. These PCPs are exponential in size and have exponentially low error. Previously, it was only known how to construct zero-knowledge PCPs with a constant error probability.

In the course of constructing these PCP's we abstract a tool we call {\em locking systems}. We provide the definition and also a locking system with very efficient parameters. This mechanism may be useful in other settings as well.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-27.ps.gz
DIMACS Home Page