The Taub Faculty of Computer Science Events and Talks

In a polynomial protocol a prover sends messages that are polynomials, and the verifier is allowed to check polynomial identities between these polynomials. The prover complexity is measured as the sum of degrees of the polynomials sent. The motivation for the definition is to capture prover complexity in zero knowledge proofs systems based on polynomial commitment schemes.

We will present and illustrate this notion; and present an open question on improved protocols for “range proofs” – where given a committed polynomial f, and subset H of the field, we wish to prove f‘s values on H, are in a bounded domain [1,…,M].

We will also attempt to give intuition as to why such range proofs are a crucial component in practical zero-knowledge systems.

(Joint work with Zachary J. Williamson)

More details.

Lecture Video.