Results 1671 - 1680 of 23856
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.
I’ll present recent progress towards constructing SNARGs for NP from standard cryptographic assumptions, without relying on indistinguishability obfuscation (iO). Specifically, we show how to build SNARGs for NP from witness encryption or designated-verifier SNARGs that have a polynomial-size proof of correctness in propositional logic, assuming learning with errors.
Based on joint works with Yael Tauman Kalai, Alex Lombardi, Surya Mathialagan, and Vinod Vaikuntanathan.
Over the past five years, there has been significant progress in constructing succinct non-interactive arguments from standard cryptographic assumptions. A key component underpinning many of these advances is the concept of batch arguments (BARGs).
In this tutorial talk, we will introduce the notion of BARGs, demonstrate how they can be used to construct succinct non-interactive arguments (SNARGs) for deterministic computations, and explore applications in which BARGs can replace general-purpose SNARKs for NP.