Theory of Computing Seminar

Thursday October 27, 2016 1:30 PM

On Probabilistic Checking in Perfect Zero Knowledge

Speaker: Michael Forbes, MIT
Location: Annenberg 213

Abstract:

The sum-check protocol of Lund, Fortnow, Karloff and Nisan is an interactive proof for #P, enabling the verifier to count the number of satisfying assignments of a boolean formula. This celebrated protocol sparked the subsequent probabilistically checkable proof (PCP) revolution. We revisit this protocol from the perspective of zero-knowledge, that is, interactive proofs that reveal no information other than their correctness.  While the protocol as-is is not zero-knowledge, fundamental work of Ben-Or, Goldreich, Goldwasser, Hastad, Kilian, Micali, and Rogaway leveraged cryptographic tools (one-way functions) to show that any interactive proof (such as sum-check) can be made zero-knowledge. However, the obtained zero-knowledge is computationally secure, as opposed to statistical (or even perfect) security.

In this work we study how to make the sum-check protocol perfect zero-knowledge, by working in an extension of the interactive proof model called interactive probabilistically checkable proofs (interactive PCPs), due to Kalai and Raz.  In this model the prover can send an exponentially long string to the verifier, which the verifier can read via random access, after which an interactive proof proceeds as usual.  While there is a natural candidate for a zero-knowledge sum-check protocol in this setting, it turns out to be non-trivial to prove the required zero-knowledge property.

To establish that this protocol is perfect zero-knowledge, we use derandomization techniques from algebraic complexity theory due to Raz-Shpilka and Bogdanov-Wee.  These algorithms efficiently and deterministically solve succinctly-described exponentially-large linear systems of equations arising from questions about low-degree polynomials, which have a natural coding-theory interpretation.

Joint work with Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael
Riabzev, and Nicholas Spooner. arxiv:1610.03798. 
Series Theory of Computing Seminar Series

Contact: Thomas Vidick vidick@cms.caltech.edu