### Sumcheck Arguments and their Applications

Jonathan Bootle, Alessandro Chiesa, and Katerina Sotiraki

##### Abstract

We introduce a class of interactive protocols, which we call *sumcheck arguments*, that establishes a novel connection between the sumcheck protocol (Lund et al. JACM 1992) and folding techniques for Pedersen commitments (Bootle et al. EUROCRYPT 2016). We define a class of sumcheck-friendly commitment schemes over modules that captures many examples of interest, and show that the sumcheck protocol applied to a polynomial associated with the commitment scheme yields a succinct argument of knowledge for openings of the commitment. Building on this, we additionally obtain succinct arguments for the NP-complete language R1CS over certain rings. Sumcheck arguments enable us to recover as a special case numerous prior works in disparate cryptographic settings (discrete logarithms, pairings, groups of unknown order, lattices), providing one framework to understand them all. Further, we answer open questions raised in prior works, such as obtaining a lattice-based succinct argument from the SIS assumption for satisfiability problems over rings.

Note: In submission.

##### Metadata
Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2021
Keywords
sumcheck protocolsuccinct argumentsscalar-product protocol
Contact author(s)
jbt @ zurich ibm com
alexch @ berkeley edu
katesot @ berkeley edu
History
2021-06-09: revised
2021-03-14: received
See all versions
Short URL
https://ia.cr/2021/333
License

CC BY

BibTeX

@misc{cryptoeprint:2021/333,
author = {Jonathan Bootle and Alessandro Chiesa and Katerina Sotiraki},
title = {Sumcheck Arguments and their Applications},
howpublished = {Cryptology ePrint Archive, Paper 2021/333},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/333}},
url = {https://eprint.iacr.org/2021/333}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.