Doctoral Speaking Skills Talk - Quang Dao
— 5:30pm
Location:
In Person
-
Blelloch-Skees Conference Room, Gates Hillman 8115
Speaker:
QUANG DAO
,
Ph.D. Student
Computer Science Department
Carnegie Mellon University
https://quangvdao.github.io/
The sum-check protocol is a fundamental interactive proof for verifying expensive claims about multivariate polynomials over a finite field. It allows an untrusted prover to demonstrate such a claim to a computationally limited verifier, providing high confidence in the validity of the claim. Introduced over three decades ago, sum-check is now at the core of the most efficient cryptographic proof systems. However, its ubiquitous usage has made sum-check a proving bottleneck in many applications.
I will present a suite of improvements to the sum-check prover that outperforms classic algorithms in many settings of interest. These improvements rely on two key ideas. First, by opening the black box of finite field arithmetic, we enable fast multiplication with small values such as 64-bit integers, which naturally arise when proving correct program execution. Second, we batch the prover's work across many consecutive rounds into a larger computation, which is beneficial in two distinct settings. When proving program execution, this approach allows us to trade expensive multiplication over the field for cheap multiplication with small values. In streaming settings, where the prover is limited in working memory, this reduces the number of passes over the input, allowing the prover to finish faster with only a minimal increase in total computation.
Joint work with Zachary DeStefano, Suyash Bagad, Yuval Domb, and Justin Thaler.
For More Information:
matthewstewart@cmu.edu