In this talk, we will show how one can verify the correctness of a computation much more efficiently than having to re-perform the computation. We will introduce the notion of succinct non-interactive argument systems (SNARK) that allow a prover to convince a verifier about the correctness of computation such that verification is exponentially faster than the computation itself, and zero-knowledge, where the verifier learns nothing beyond the truth of the statement. We will outline the design principle underlying SNARK constructions that use a cryptographic compiler on an information-theoretic proof system.  Many popular SNARKs use Polynomial Interactive Oracle Proofs (PIOPs) as the information-theoretic component, and then compile the PIOP into a succinct argument system using a cryptographic tool called a Polynomial Commitment Scheme (PCS).We then provide a framework for transforming a univariate polynomial commitment scheme into a multilinear polynomial commitment scheme. The transformation is generic, can be instantiated with any univariate scheme and improves on prior transformations in all relevant parameters: proof size, verification complexity, and prover complexity.

Short Bio: Chaya Ganesh is an Associate Professor in the Department of Computer Science and Automation at Indian Institute of Science . Before joining IISc, she was a post-doctoral researcher in Aarhus University, and prior to that she received her PhD from NYU's Courant Institute of Mathematical Sciences.Her research interests are broadly in Cryptography and Security. She has won the IBM global university award, Google and Protocol labs research grants, Infosys Young investigator award and Intel Rising Star Faculty award.