A common relaxation is a \emph{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 contribution is three-fold:
(1) We introduce and study a natural extension of the interactive proof model that considers \emph{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) \emph{linear-interactive proofs} (LIPs) for NP. Our constructions are based on general transformations applied to both \emph{linear} PCPs (LPCPs) and traditional ``unstructured" PCPs.
(2) We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of \emph{linear targeted malleability} (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain \emph{zero-knowledge} LIPs and SNARGs. Our techniques yield SNARGs \emph{of knowledge} and thus can benefit from known recursive composition and bootstrapping techniques.
(3) Following this methodology, we exhibit several constructions achieving new efficiency features, such as ``single-ciphertext preprocessing SNARGs" and improved succinctness-soundness tradeoffs. We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.
Category / Keywords: foundations / interactive proofs, probabilistically-checkable proofs, succinct arguments, homomorphic encryption, zero-knowledge Publication Info: TCC 2013 Date: received 23 Dec 2012, last revised 15 Sep 2013 Contact author: alexch at mit edu Available format(s): PDF | BibTeX Citation Note: fixed some typos in revised version Version: 20130915:160301 (All versions of this report) Short URL: ia.cr/2012/718