A divide-and-conquer sumcheck protocol
Authors
Christophe Levrat, Tanguy Medevielle, Jade Nardi
Christophe Levrat
INRIA Saclay, Palaiseau, France
christophe dot levrat at math dot cnrs dot fr
christophe dot levrat at math dot cnrs dot fr
Tanguy Medevielle
Univ Rennes, CNRS, IRMAR - UMR 6625, F-35000, Rennes, France
tanguy dot medevielle at univ-rennes dot fr
tanguy dot medevielle at univ-rennes dot fr
Jade Nardi
Univ Rennes, CNRS, IRMAR - UMR 6625, F-35000, Rennes, France
jade dot nardi at univ-rennes dot fr
jade dot nardi at univ-rennes dot fr
Abstract
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.
References
[ACY23]
Gal Arnon, Alessandro Chiesa, and Eylon Yogev. IOPs with inverse polynomial soundness error. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 752–761. 2023. IEEE. DOI: 10.1109/FOCS57990.2023.00050
[AFK23]
Thomas Attema, Serge Fehr, and Michael Klooß. Fiat–Shamir Transformation of Multi-Round Interactive Proofs (Extended Version). Journal of Cryptology, 36(4):36, 2023. DOI: 10.1007/s00145-023-09478-y
[BCS21]
Jonathan Bootle, Alessandro Chiesa, and Katerina Sotiraki. Sumcheck arguments and their applications. In Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part I 41, pages 742–773. 2021. Springer. DOI: 10.1007/978-3-030-84242-0_26
[BFLS91]
László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pages 21–32, New York, NY, USA. 1991. Association for Computing Machinery. DOI: 10.1145/103418.103428
[BFS20]
Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent SNARKs from DARK compilers. In Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part I 39, pages 677–706. 2020. Springer. DOI: 10.1007/978-3-030-45721-1_24
[BSBHR18]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:17, Dagstuhl, Germany. 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.ICALP.2018.14
[BSBHR19]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable Zero Knowledge with No Trusted Setup. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, pages 701–732, Cham. 2019. Springer International Publishing. DOI: 10.1007/978-3-030-26954-8_23
[BSCR+19]
Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent Succinct Arguments for R1CS. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 103–128, Cham. 2019. Springer International Publishing. DOI: 10.1007/978-3-030-17653-2_4
[BSCS16]
Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Theory of Cryptography: 14th International Conference, TCC 2016-B, Beijing, China, October 31-November 3, 2016, Proceedings, Part II 14, pages 31–60. 2016. Springer. DOI: 10.1007/978-3-662-53644-5_2
[CCH+18]
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, and Ron D. Rothblum. Fiat-Shamir From Simpler Assumptions. Cryptology ePrint Archive, Paper 2018/1004. 2018.
[DL78]
Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. DOI: https://doi.org/10.1016/0020-0190(78)90067-4
[GKR15]
Shafi Goldwasser, Yael Tauman Kalai, and Guy N Rothblum. Delegating computation: interactive proofs for muggles. Journal of the ACM (JACM), 62(4):1–64, 2015.
[GLS+23]
Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, pages 193–226, Cham. 2023. Springer Nature Switzerland. DOI: 10.1007/978-3-031-38545-2_7
[GMR89]
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing, 18(1):186-208, 1989. DOI: 10.1137/0218012
[KT24]
Tohru Kohrita and Patrick Towa. Zeromorph: Zero-knowledge multilinear-evaluation proofs from homomorphic univariate commitments. Journal of Cryptology, 37(4):38, 2024. DOI: 10.1007/s00145-024-09519-0
[KZG10]
Aniket Kate, Gregory M Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16, pages 177–194. 2010. Springer. DOI: 10.1007/978-3-642-17373-8_11
[Lee21]
Jonathan Lee. Dory: Efficient, Transparent Arguments for Generalised Inner Products and Polynomial Commitments. In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography, pages 1–34, Cham. 2021. Springer International Publishing. DOI: 10.1007/978-3-030-90453-1_1
[LFKN92]
Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM (JACM), 39(4):859–868, 1992. DOI: 10.1145/146585.14660
[MF21]
Arno Mittelbach and Marc Fischlin. The theory of hash functions and random oracles. An Approach to Modern Cryptography, Cham: Springer Nature, 2021. DOI: 10.1007/978-3-030-63287-8
[NST24]
Vineet Nair, Ashish Sharma, and Bhargav Thankey. BrakingBase-a linear prover, poly-logarithmic verifier, field agnostic polynomial commitment scheme. Cryptology ePrint Archive, 2024.
[Sch80]
J. T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM, 27(4):701–717, October 1980. DOI: 10.1145/322217.322225
[Set20]
Srinath Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In Annual International Cryptology Conference, pages 704–737. 2020. Springer. DOI: 10.1007/978-3-030-56877-1_25
[Tha22]
Justin Thaler. Proofs, arguments, and zero-knowledge. Foundations and Trends® in Privacy and Security, 4(2–4):117–660, 2022. DOI: 10.1561/3300000030
[WTS+18]
Riad S Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, and Michael Walfish. Doubly-efficient zkSNARKs without trusted setup. In 2018 IEEE Symposium on Security and Privacy (SP), pages 926–943. 2018. IEEE. DOI: 10.1109/SP.2018.00060
[ZCF24]
Hadas Zeilberger, Binyi Chen, and Ben Fisch. BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, pages 138–169, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-68403-6_5
[Zip79]
Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng, editor, Symbolic and Algebraic Computation, pages 216–226, Berlin, Heidelberg. 1979. Springer Berlin Heidelberg. DOI: 10.1007/3-540-09519-5_73
PDF
History
Submitted: 2025-01-07
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Christophe Levrat, Tanguy Medevielle, and Jade Nardi, A divide-and-conquer sumcheck protocol. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/abksdk5vt.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.