Paper 2021/1673
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead
Noga RonZewi and Ron D. Rothblum
Abstract
Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input $x$ belongs to a language $L \in NP$, with communication that is much shorter than the $NP$ witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of \emph{proving} correctness. In this work we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fanin), with a \emph{strictly linear} size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a \emph{quasi}linear size prover for general Boolean circuits or with linearsize only for arithmetic circuits, defined over large finite fields. In more detail, for every Boolean circuit $C=C(x,w)$, we construct an $O(\log C)$round argumentsystem in which the prover can be implemented by a size $O(C)$ Boolean circuit (given as input both the instance $x$ and the witness $w$), with arbitrarily small constant soundness error and using $poly(\lambda,\log C)$ communication, where $\lambda$ denotes the security parameter. The verifier can be implemented by a size $O(x) + poly(\lambda, \log C)$ circuit following a size $O(C)$ private preprocessing step, or, alternatively, by using a purely publiccoin protocol (with no preprocessing) with a size $O(C)$ verifier. The protocol can be made zeroknowledge using standard techniques (and with similar parameters). The soundness of our protocol is computational and relies on the existence of collision resistant hash functions that can be computed by linearsize circuits, such as those proposed by Applebaum et al. (ITCS, 2017). At the heart of our construction is a new informationtheoretic \emph{interactive oracle proof} (IOP), an interactive analog of a PCP, for circuit satisfiability, with constant prover overhead. The improved efficiency of our IOP is obtained by bypassing a barrier faced by prior IOP constructions, which needed to (either explicitly or implicitly) encode the entire computation using a multiplication code.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint.
 Keywords
 Succinct arguments
 Contact author(s)

rothblum @ cs technion ac il
noga @ cs haifa ac il  History
 20211221: received
 Short URL
 https://ia.cr/2021/1673
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1673, author = {Noga RonZewi and Ron D. Rothblum}, title = {Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead}, howpublished = {Cryptology ePrint Archive, Paper 2021/1673}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1673}}, url = {https://eprint.iacr.org/2021/1673} }