Title: A Zero Knowledge Sumcheck and its Applications,
Abstract: Many seminal results in Interactive Proofs (IPs) use algebraic techniques
based on low-degree polynomials, the study of which is pervasive in theoretical
computer science. Unfortunately, known methods for endowing such proofs with
zero knowledge guarantees do not retain this rich algebraic structure.
In this work, we develop algebraic techniques for obtaining zero knowledge
variants of proof protocols in a way that leverages and preserves their
algebraic structure. Our constructions achieve unconditional (perfect) zero
knowledge in the Interactive Probabilistically Checkable Proof (IPCP) model of
Kalai and Raz [KR08] (the prover first sends a PCP oracle, then the prover and
verifier engage in an Interactive Proof in which the verifier may query the
PCP).
Our main result is a zero knowledge variant of the sumcheck protocol [LFKN92]
in the IPCP model. The sumcheck protocol is a key building block in many IPs,
including the protocol for polynomial-space computation due to Shamir [Sha92],
and the protocol for parallel computation due to Goldwasser, Kalai, and
Rothblum [GKR15]. A core component of our result is an algebraic commitment
scheme, whose hiding property is guaranteed by algebraic query complexity lower
bounds [AW09,JKRS09]. This commitment scheme can then be used to considerably
strengthen our previous work [BCFGRS16] that gives a sumcheck protocol with
much weaker zero knowledge guarantees, itself using algebraic techniques based
on algorithms for polynomial identity testing [RS05,BW04].
We demonstrate the applicability of our techniques by deriving zero knowledge
variants of well-known protocols based on algebraic techniques, including the
protocols of Shamir and of Goldwasser, Kalai, and Rothblum, as well as the
protocol of Babai, Fortnow, and Lund [BFL91].