International Association
for Cryptologic Research

\\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.