Title: Succinct Non-Interactive Arguments via Linear Interactive Proofs
Speaker: Alessandro Chiesa (MIT)
Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation.
A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have “escaped the hegemony” of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments.
We present a general methodology for the construction of preprocessing SNARGs, as well as resulting concrete efficiency improvements. Our results are achieved by studying a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded “adversaries” in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear-interactive proofs (LIPs) for NP. We then show how to generically compile LIPs into preprocessing SNARGs.
Joint work with Nir Bitansky, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth.