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.
Category / Keywords: cryptographic protocols / sumcheck protocol; succinct arguments; scalar-product protocol Original Publication (with major differences): IACR-CRYPTO-2021 Date: received 14 Mar 2021, last revised 9 Jun 2021 Contact author: jbt at zurich ibm com,alexch@berkeley edu,katesot@berkeley edu Available format(s): PDF | BibTeX Citation Note: In submission. Version: 20210609:130632 (All versions of this report) Short URL: ia.cr/2021/333