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 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 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 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 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.
Last modified: Thu, 27 Dec 2012 16:41:46 -0500