Theory of Computing Seminar
On Probabilistic Checking in Perfect Zero Knowledge
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.
Contact: Thomas Vidick firstname.lastname@example.org