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.
DIMACS Home Page