Lali Devadas, Batching Adaptively-Sound SNARGs for NP

Speaker: Lali Devadas, MIT

Date: Friday, September 20, 2024

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

Public: Yes

Location: 32-G882 Hewlett

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan and Yael Kalai

Contact: Meenu Tiwari, meenu@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Lali Devadas, Batching Adaptively-Sound SNARGs for NP

A succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement is true with a proof whose size is sublinear in the length of its NP witness. Moreover, a SNARG is adaptively sound if the adversary can choose the statement it wants to prove after seeing the scheme's public parameters. Recently, Waters and Wu (STOC 2024) showed how to construct adaptively-sound SNARGs for NP in the plain model from falsifiable assumptions (specifically, sub-exponentially secure indistinguishability obfuscation, sub-exponentially secure one-way functions, and polynomial hardness of the discrete log assumption).
We consider the batch setting where the prover wants to certify a collection of statements and its goal is to construct a proof whose size is sublinear in both the size of a single witness and the number of statements. All existing adaptively-sound constructions either require the size of the public parameters to scale linearly with the number of statements or have proof size that scales linearly with the size of a single NP witness. In this work, we show that under the same set of assumptions as those underlying the Waters-Wu adaptively-sound SNARG, we can obtain an adaptively-sound SNARG for batch-NP where the size of the proof is poly(k) and the size of the public parameters is poly(k+|C|), where k is a security parameter and |C| is the size of the circuit that computes the associated NP relation.

We give two approaches for batching adaptively-sound SNARGs for NP. Our first approach builds directly on top of the Waters-Wu construction and relies on indistinguishability obfuscation and a homomorphic re-randomizable one-way function. Our second approach shows how to combine ideas from the Waters-Wu SNARG with the chaining-based approach by Garg, Sheridan, Waters, and Wu (TCC 2022) and avoids relying on a structure like homomorphism.

Joint work with Brent Waters (UT Austin and NTT Research) and David J. Wu (UT Austin).

Research Areas:

Impact Areas:

See other events that are part of the CIS Seminar Series 2023 - 2024.

Created by Meenu Tiwari at Thursday, September 12, 2024 at 9:51 AM.