International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Sumcheck Arguments and their Applications

Authors:
Jonathan Bootle , IBM Research Zurich
Alessandro Chiesa , UC Berkeley
Katerina Sotiraki , UC Berkeley
Download:
Search ePrint
Search Google
Conference: CRYPTO 2021
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). Informally, we consider a general notion of bilinear commitment over modules, and show that the sumcheck protocol applied to a certain 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 (such as discrete logarithms, pairings, RSA groups, lattices), providing one abstract 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.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31196,
  title={Sumcheck Arguments and their Applications},
  publisher={Springer-Verlag},
  author={Jonathan Bootle and Alessandro Chiesa and Katerina Sotiraki},
  year=2021
}