Seminar Details
Highly-efficient Interactive Oracle Proofs & Cryptographic Applications
- Start Date: April 6, 2022
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Noga Ron-Zewi - University of Haifa
- Event Location: Online Event
- Event Additional Info: <p>Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar" target="_blank">https://theory.cs.rutgers.edu/theory_seminar</a> </p>
- Presentation Type: Stand Alone Presentation
- 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.