Zero Knowledge for Free up to Linear Query Bounds: Quasilinear-Size Constant-Query Zero-Knowledge PCPs

We show that for all polynomials $T$ and $b$, every relation in NTIME($T$) has a binary PCP with $O(1)$ non-adaptive queries, perfect completeness, soundness error 1/2 and length $(T+b)\cdot(\log(T+b))^{O(1)}$, which is perfect zero knowledge against every adaptive, possibly malicious verifier makin