Succinct Arguments from
Multi-Prover Interactive Proofs and their
Efficiency Benefits
Nir Bitansky (
Alessandro Chiesa
(MIT)
Abstract:
Succinct arguments of knowledge are computationally-sound proofs of knowledge
for NP where the verifier’s running time is independent of the time
complexity of the NP nondeterministic machine for the considered language.
Existing succinct argument constructions are, typically, based on techniques
that combine cryptographic hashing and probabilistically-checkable proofs
(PCPs), and thus, in light of today’s state-of-the-art PCP technology,
are quite inefficient: either one uses long PCP proofs with lots of
redundancy to make the verifier fast but at the cost of making the prover slow, or one uses short PCP proofs to make the prover fast but at the cost of making the verifier slow.
To obtain better efficiency, we propose to 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 protocol where (i) each prover is highly
efficient in terms of time AND space, and ALSO (ii) the verifier is highly
efficient.
(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.
As a main tool for this transformation, we 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
rule out solutions based on black-box reductions to standard assumptions. We
formulate a natural (though non-standard) variant of homomorphic
encryption that has a homomorphism- extraction property. We then show that
his primitive essentially allows to “squash”
our interactive protocol, while again preserving time and space efficiency.
We further show that this variant is, in fact, implied by the existence of SNARKs.