A Zero-Knowledge PCP Theorem

Tom Gur, Jack O'Connor, Nicholas Spooner

We show that for every polynomial q* there exist polynomial-size, constant-query, non-adaptive PCPs for NP which are perfect zero knowledge against (adaptive) adversaries making at…