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] presents two algorithms, the first of which uses logarithmic space but runs in superlinear time; the latter 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
Note: Update acks and related works.
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-09-11: last of 2 revisions
- 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},
url = {https://eprint.iacr.org/2024/524}
}
