Probabilistically checkable proofs with zero knowledge
Joe Kilian, Erez Petrank, Gábor Tardos · 1997
We construct PCPS with strong zero-knowledge properties.First, we construct polynomially bounded (in size) PCP'S for NP which can be checked using poly-Iogarithmic 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 NEXPTIME that can be checked using polynomially many queries, yet are statistically zero-knowledge against any polynomial y 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 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.