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. 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 n1/2 + o(1)· poly(λ), where n 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. Previously, we only had non-adaptively sound SNAPs for P in the designated verifier setting with O(n1−δ) proof size, query complexity, and verification time for some constant δ > 0. We show that our parameters in the adaptive soundness setting are nearly optimal, up to an no(1) · poly(λ) factor: in any adaptive SNAP for P, the product of proof size and verifier query complexity must be Ω(n). Our lower bound is unconditional. 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.