אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

A probabilistically checkable proof (PCP) enables checking, for example, the satisfiability of a 3-SAT boolean formula phi, while only examining a constant number of randomly chosen symbols of the proof. Suppose an assignment to phi has length n. A long line of research led to the construction of such PCPs of length quasi-linear in n.

An additional property of a PCP that can be useful is that of zero-knowledge (ZK): A PCP is zero-knowledge with knowledge bound K, if reading any K symbols of the proof reveals no additional information besides the validity of the statement; for example, no information is revealed about the assignment satisfying phi.

Kilian, Petrank and Tardos, gave a generic way to transform any PCP into a ZK-PCP with knowledge bound K, for any desired K. A drawback of their transformation is that it requires multiplying the proof length by a factor of (at least) K^6.

In this work, we show how to construct PCPs that are zero knowledge for knowledge bound K and of length quasi-linear in K and n - provided the prover is forced to write the proof in two rounds. In this model, which we call duplex PCP (DPCP), the verifier gets an oracle string from the prover, then replies with some randomness, and then gets another oracle string from the prover, and it can make up to K queries to both oracles.

Deviating from previous works, our constructions do not invoke the PCP Theorem as a blackbox but rather rely on certain algebraic properties of a specific family of PCPs. We show that if the PCP has a certain linear algebraic structure --- which many central constructions can be shown to possess, including {BFLS91,ALMSS98, BS08} --- we can add the zero knowledge property at virtually no cost (up to additive lower order terms) while introducing only minor modifications in the algorithms of the prover and verifier. We believe our linear-algebraic characterization of PCPs may be of independent interest, as it gives a simplified way to view previous well-studied PCP constructions.

Joint work with Eli Ben-Sasson, Alessandro Chiesa and Madars Virza