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

Inhyuk Park, Chenglin Fan

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 $…