Paper 2022/994

Faster Sounder Succinct Arguments and IOPs

Justin Holmgren, NTT Research
Ron Rothblum, Technion – Israel Institute of Technology
Abstract

Succinct arguments allow a prover to convince a verifier that a given statement is true, using an extremely short proof. A major bottleneck that has been the focus of a large body of work is in reducing the overhead incurred by the prover in order to prove correctness of the computation. By overhead we refer to the cost of proving correctness, divided by the cost of the original computation. In this work, for a large class of Boolean circuits $C=C(x,w)$, we construct succinct arguments for the language $\{ x : \exists w\; C(x,w)=1\}$, with $2^{-\lambda}$ soundness error, and with prover overhead $\mathsf{polylog}(\lambda)$. This result relies on the existence of (sub-exponentially secure) linear-size computable collision-resistant hash functions. The class of Boolean circuits that we can handle includes circuits with a repeated sub-structure, which arise in natural applications such as batch computation/verification, hashing and related block chain applications. The succinct argument is obtained by constructing \emph{interactive oracle proofs} for the same class of languages, with $\mathsf{polylog}(\lambda)$ prover overhead, and soundness error $2^{-\lambda}$. Prior to our work, the best IOPs for Boolean circuits either had prover overhead of $\mathsf{polylog}(|C|)$ based on efficient PCPs due to Ben-Sasson et al. (STOC, 2013) or $\mathsf{poly}(\lambda)$ due to Rothblum and Ron-Zewi (STOC, 2022).

Note: Re-added section 5.1 which was missing due to a compilation problem.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2022
Keywords
IOPsProofsArgumentsSNARKsSNARGs
Contact author(s)
justin holmgren @ ntt-research com
rothblum @ cs technion ac il
History
2023-02-25: revised
2022-08-03: received
See all versions
Short URL
https://ia.cr/2022/994
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2022/994,
      author = {Justin Holmgren and Ron Rothblum},
      title = {Faster Sounder Succinct Arguments and IOPs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/994},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/994}},
      url = {https://eprint.iacr.org/2022/994}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.