A divide-and-conquer sumcheck protocol
IACR Communications in Cryptology · 08.04.2025 · 2 (1)
DOI: 10.62056/abksdk5vt ↗Kurz gefasst
Studienprotokoll in der Zeitschrift IACR Communications in Cryptology, online erschienen am 08.04.2025. Verfasst von Christophe Levrat und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We present a new sumcheck protocol called Fold-DCS (Fold-Divide-and-Conquer-Sumcheck) for multivariate polynomials based on a divide-and-conquer strategy. Its round complexity and soundness error are logarithmic in the number of variables, whereas they are linear in the classical sumcheck protocol. This drastic improvement in number of rounds and soundness comes at the expense of exchanging multivariate polynomials, which can be alleviated using polynomial commitment schemes. We first present Fold-DCS in the PIOP model, where the prover provides oracle access to a multivariate polynomial at each round. We then replace this oracle access in practice with a multivariate polynomial commitment scheme; we illustrate this with an adapted version of the recent commitment scheme Zeromorph, which allows us to replace most of the queries made by the verifier with a single batched evaluation check.
Zitieren
APA
Levrat, C., Medevielle, T., & Nardi, J. (2025). A divide-and-conquer sumcheck protocol. IACR Communications in Cryptology, 2(1). https://doi.org/10.62056/abksdk5vt
Vancouver
Levrat C, Medevielle T, Nardi J. A divide-and-conquer sumcheck protocol. IACR Communications in Cryptology. 2025;2(1). doi:10.62056/abksdk5vt
BibTeX
@article{Levrat2025,
author = {Levrat, Christophe and Medevielle, Tanguy and Nardi, Jade},
title = {A divide-and-conquer sumcheck protocol},
journal = {IACR Communications in Cryptology},
year = {2025},
volume = {2},
number = {1},
doi = {10.62056/abksdk5vt}
}
EUVIMED