Paper 2024/524
A Time-Space Tradeoff for the Sumcheck Prover
, École Polytechnique Fédérale de LausanneAbstract
The sumcheck protocol is an interactive protocol for verifying the sum of a low-degree polynomial over a hypercube. This protocol is widely used in practice, where an efficient implementation of the (honest) prover algorithm is paramount. Prior work contributes highly-efficient prover algorithms for the notable special case of multilinear polynomials (and related settings): [CTY11] uses logarithmic space but runs in superlinear time; in contrast, [VSBW13] runs in linear time but uses linear space. In this short note, we present a family of prover algorithms for the multilinear sumcheck protocol that offer new time-space tradeoffs. In particular, we recover the aforementioned algorithms as special cases. Moreover, we provide an efficient implementation of the new algorithms, and our experiments show that the asymptotics translate into new concrete efficiency tradeoffs.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Contact author(s)
-
alessandro chiesa @ epfl ch
efedele @ ethz ch
giacomo fenzi @ epfl ch
andrew zitek @ epfl ch - History
- 2024-04-06: approved
- 2024-04-03: received
- See all versions
- Short URL
- https://ia.cr/2024/524
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/524,
author = {Alessandro Chiesa and Elisabetta Fedele and Giacomo Fenzi and Andrew Zitek-Estrada},
title = {A Time-Space Tradeoff for the Sumcheck Prover},
howpublished = {Cryptology ePrint Archive, Paper 2024/524},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/524}},
url = {https://eprint.iacr.org/2024/524}
}
