From Secure Computation to Zero-Knowledge Probabilistic Checking and Back Again

מור וייס, הרצאה סמינריונית לדוקטורט
יום רביעי, 6.4.2016, 12:30
טאוב 201
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.

בחזרה לאינדקס האירועים