Succinct Non-interactive Arguments of Proximity

We study succinct non-interactive arguments of proximity (SNAPs), which allow a prover to convince a verifier that a statement is true via a short message. The verifier reads only a sublinear number of bits of the statement. Soundness holds against polynomial-time adversaries and guarantees that the statement is "close" in hamming distance to a true statement. SNAPs enable verification of extremely long statements without reading them entirely.  We obtain the following results:

 - For adaptive soundness, we construct SNAPs for P with proof length, verifier's query complexity, and verification time roughly O(n^(1/2)) from (e.g.,) LWE. We extend these to NP by additionally using indistinguishability obfuscation. We also prove our parameters are nearly optimal.

 - For non-adaptive settings, we construct fully succinct SNAPs for NP with poly(lambda) proof length, query complexity, and verification time based on LWE and indistinguishability obfuscation. 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.

Based on a joint work with Liyan Chen and Zhengzhong Jin in STOC 2025.