Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead

Speaker: Ron Rothblum

Date: Friday, March 18, 2022

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G-882 Hewlett Room

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan, Yael Kalai

Contact: Felicia Raton, 401-580-5009, fraton@csail.mit.edu

Relevant URL:

Speaker URL: http://www.cs.technion.ac.il/~rothblum/

Speaker Photo:

Reminders to: fraton@mit.edu

Reminder Subject: TALK: Ron Rothblum: Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input x belongs to a language L \in NP, with communication that is much shorter than the NP witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of proving correctness.

In this work we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fan-in), with a strictly linear size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a quasi-linear size prover for general Boolean circuits or with linear-size only for arithmetic circuits, defined over large finite fields.

Joint work Noga Ron-Zewi.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information (CIS) Seminar 2022.

Created by Felicia Raton at Monday, March 14, 2022 at 11:23 AM.