Welcome to the resource topic for 2012/461
Title:
Succinct Arguments from Multi-Prover Interactive Proofs and their Efficiency Benefits
Authors: Nir Bitansky, Alessandro Chiesa
Abstract:\emph{Succinct arguments of knowledge} are computationally-sound proofs of knowledge for NP where the verifier’s running time is independent of the time complexity t of the nondeterministic NP machine M that decides the given language. Existing succinct argument constructions are, typically, based on techniques that combine cryptographic hashing and probabilistically-checkable proofs (PCPs). Yet, even when instantiating these constructions with state-of-the-art PCPs, the prover needs \Omega(t) space in order to run in quasilinear time (i.e., time t \poly(k)), regardless of the space complexity s of the machine M. We say that a succinct argument is \emph{complexity preserving} if the prover runs in time t \poly(k) and space s \poly(k) and the verifier runs in time |x| \poly(k) when proving and verifying that a t-time s-space random-access machine nondeterministically accepts an input x. Do complexity-preserving succinct arguments exist? To study this question, we investigate the alternative approach of constructing succinct arguments based on multi-prover interactive proofs (MIPs) and stronger cryptographic techniques: (1) We construct a one-round succinct MIP of knowledge, where each prover runs in time t \polylog(t) and space s \polylog(t) and the verifier runs in time |x| \polylog(t). (2) We show how to transform any one-round MIP protocol to a succinct four-message argument (with a single prover), while preserving the time and space efficiency of the original MIP protocol; using our MIP protocol, this transformation yields a complexity-preserving four-message succinct argument. As a main tool for our transformation, we define and construct a \emph{succinct multi-function commitment} that (a) allows the sender to commit to a vector of functions in time and space complexity that are essentially the same as those needed for a single evaluation of the functions, and (b) ensures that the receiver’s running time is essentially independent of the function. The scheme is based on fully-homomorphic encryption (and no additional assumptions are needed for our succinct argument). (3) In addition, we revisit the problem of \emph{non-interactive} succinct arguments of knowledge (SNARKs), where known impossibilities prevent solutions based on black-box reductions to standard assumptions. We formulate a natural (but non-standard) variant of homomorphic encryption having a \emph{homomorphism-extraction property}. We show that this primitive essentially allows to squash our interactive protocol, while again preserving time and space efficiency, thereby obtaining a complexity-preserving SNARK. We further show that this variant is, in fact, implied by the existence of (complexity-preserving) SNARKs.
ePrint: https://eprint.iacr.org/2012/461
Talk: https://www.youtube.com/watch?v=vr6STbqoqC8
Slides: https://iacr.org/cryptodb/archive/2012/CRYPTO/presentation/4-2-Chiesa.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .