Noga Ron-Zewi, University of Haifa

Abstract

Interactive oracle proofs (IOPs) extend the classic notion of probabilistically-checkable proofs (PCPs) by allowing a verifier to interact with a prover over a small number of rounds while querying the prover’s messages in only a few locations.

A recent line of work gave highly-efficient IOPs bypassing state-of-the-art PCPs, for example, constant-round and constant-query IOPs with only a linear (and even approaching the witness length) amount of communication, as well as IOPs with linear-time prover complexity. These constructions were leveraged in turn to obtain highly-efficient succinct arguments and zero-knowledge proofs.

The improved efficiency was obtained by replacing polynomial-based codes, commonly used in such proof systems, with more efficient (tensor-based) codes. In particular, these constructions bypassed a barrier imposed by the need to encode the computation using a multiplication code.

In the talk, I will survey these highly-efficient IOP constructions and their cryptographic applications.

Based on Joint works with Ron Rothblum, appearing in FOCS 2020, and to appear in STOC 2022.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar