Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

From Secure Computation to Zero-Knowledge Probabilistic Checking and Back Again
event speaker icon
Mor Weiss (Ph.D. Thesis Seminar)
event date icon
Wednesday, 06.04.2016, 12:30
event location icon
Taub 201
event speaker icon
Advisor: Prof. Y. Ishai
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.