Back to Events

Succinct Non-interactive Arguments of Proximity

Speaker

Liyan Chen
MIT

Host

Vinod Vaikuntanathan and Yael Kalai
CSAIL

September 26 2025

10:30A - 12:00P

Location

32-G882

We study succinct non-interactive arguments of proximity (SNAP), which allow a prover to convince a verifier that a statement is true through a short message. Moreover, the verifier reads only a sublinear number of bits of the statement, and soundness is required to hold against polynomial-time adversaries when the statement is πœ€-far from any true statements. SNAPs can be seen as the natural analog of property testing in the context of succinct non-interactive arguments (SNARGs). 

We obtain both positive and negative results for SNAPs.

β€’ Adaptive SNAPs for P and NP: For any πœ€ ∈ (0, 1), we construct the first adaptively sound SNAPs for P with πœ€-proximity based on standard assumptions: LWE or subexponential DDH or DLIN over bilinear maps. Our proof size, verifier’s query complexity, and verification time are 𝑛^{1/2+π‘œ(1)} poly(πœ†), where 𝑛 is the length of the statement and πœ† is the security parameter. By additionally assuming sub-exponentially secure indistinguishability obfuscation, we upgrade this result to SNAPs for NP with essentially the same parameters.


β€’ Lower Bound: We show that our parameters in the adaptive soundness setting are nearly optimal, up to an 𝑛^{π‘œ(1)}poly(πœ†) factor. Our lower bound is unconditional.


β€’ Fully Succinct Non-adaptive SNAPs for NP: For any constant πœ€ ∈ (0, 1), we construct the first non-adaptively sound SNAPs for NP with πœ€-proximity, based on learning with errors and indistinguishability obfuscation. The proof size, verifier’s query complexity, and verification time in our constructions are fixed polynomials in the security parameter. We also show that restricting such SNAPs to just P would already imply non-adaptively sound SNARGs for NP.


Central to our SNAP constructions is a new notion of commitment of proximity, which enables sublinear-time verification of the commitment. To derive our unconditional lower bound, we adopt and generalize theorems from oracle-presampling techniques in the random oracle literature. Both techniques may be of independent interest.

Joint work with Zhengzhong Jin and Daniel Wichs (Northeastern University).

Add to Calendar 2025-09-26 10:30:00 2025-09-26 12:00:00 America/New_York Succinct Non-interactive Arguments of Proximity We study succinct non-interactive arguments of proximity (SNAP), which allow a prover to convince a verifier that a statement is true through a short message. Moreover, the verifier reads only a sublinear number of bits of the statement, and soundness is required to hold against polynomial-time adversaries when the statement is πœ€-far from any true statements. SNAPs can be seen as the natural analog of property testing in the context of succinct non-interactive arguments (SNARGs). We obtain both positive and negative results for SNAPs.β€’ Adaptive SNAPs for P and NP: For any πœ€ ∈ (0, 1), we construct the first adaptively sound SNAPs for P with πœ€-proximity based on standard assumptions: LWE or subexponential DDH or DLIN over bilinear maps. Our proof size, verifier’s query complexity, and verification time are 𝑛^{1/2+π‘œ(1)} poly(πœ†), where 𝑛 is the length of the statement and πœ† is the security parameter. By additionally assuming sub-exponentially secure indistinguishability obfuscation, we upgrade this result to SNAPs for NP with essentially the same parameters.β€’ Lower Bound: We show that our parameters in the adaptive soundness setting are nearly optimal, up to an 𝑛^{π‘œ(1)}poly(πœ†) factor. Our lower bound is unconditional.β€’ Fully Succinct Non-adaptive SNAPs for NP: For any constant πœ€ ∈ (0, 1), we construct the first non-adaptively sound SNAPs for NP with πœ€-proximity, based on learning with errors and indistinguishability obfuscation. The proof size, verifier’s query complexity, and verification time in our constructions are fixed polynomials in the security parameter. We also show that restricting such SNAPs to just P would already imply non-adaptively sound SNARGs for NP.Central to our SNAP constructions is a new notion of commitment of proximity, which enables sublinear-time verification of the commitment. To derive our unconditional lower bound, we adopt and generalize theorems from oracle-presampling techniques in the random oracle literature. Both techniques may be of independent interest.Joint work with Zhengzhong Jin and Daniel Wichs (Northeastern University). TBD

Organizer & Contact

Meenu Tiwari

Part of

Related Events