Paper 2012/718

Succinct Non-Interactive Arguments via Linear Interactive Proofs

Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth

Abstract

\emph{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 researches have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. 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.

Note: fixed some typos in revised version

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. TCC 2013
Keywords
interactive proofsprobabilistically-checkable proofssuccinct argumentshomomorphic encryptionzero-knowledge
Contact author(s)
alexch @ mit edu
History
2013-09-15: revised
2012-12-27: received
See all versions
Short URL
https://ia.cr/2012/718
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/718,
      author = {Nir Bitansky and Alessandro Chiesa and Yuval Ishai and Rafail Ostrovsky and Omer Paneth},
      title = {Succinct Non-Interactive Arguments via Linear Interactive Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2012/718},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/718}},
      url = {https://eprint.iacr.org/2012/718}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.