I only have a (very) introductory knowledge about the Hardness of Approximation and PCP theorem, and I am wondering if it has any specific implications (or can somehow be studied) with Zero Knowledge Proofs?
How are PCPs and ZKPs related?
pcp;zero knowledge;intuition
PCPs are very often used to construct ZKPs, especially for NP-complete languages. The idea is simple: you commit to every bit of PCP separately, and then the prover makes random queries to the PCP. Given the query and committed bit, you prove in ZK that the bits in concrete locations would make the prover to accept. Since the number of queries is small, the proof is relatively efficient.The main problem tends to be the computational complexity: generating a PCP for an arbitrary NP language is efficient only in theory, and thus people look for more efficient solution.A recent related paper, that does something in between is by Bitansky and others (TCC 2013) where they study linear PCPs and their relation to ZK. Since linear PCPs (see their paper) are less stringent than general PCPs, they can be constructed more efficiently.