- Lali Devadas, Batching Adap...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in September 2024

## 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:**

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