The Taub Faculty of Computer Science Events and Talks

In the past few decades, probabilistic checking techniques were shown to yield dramatic efficiency improvements in verifying proofs and approximating distance from error-correcting codes. We show connections between cryptography and ``zero-knowledge'' variants of these techniques, such as Probabilistically Checkable Proofs (PCPs) and PCPs of Proximity (PCPPs), and use them to improve the complexity of cryptographic protocols. In this talk we will present three results: 1. PCPs for NP with zero-knowledge guarantees, that can be verified \emph{non-adaptively}, namely by making a single round of queries to the proof. Our construction is based on a novel connection to leakage-resilient circuits. 2. Zero-knowledge PCPPs for NP, a generalization of zero-knowledge PCPs, which we construct by combining standard PCPPs with secure multiparty computation protocols. 3. Applications of ``zero-knowledge'' probabilistic verification techniques for verifying a shared secret with a small amount of communication.