Paper 2024/524 Original: eprint.iacr.org/2024/524 ↗
A Time-Space Tradeoff for the Sumcheck Prover
Abstract
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
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2024-09-11: last updated
- 2024-04-03: published
- Short URL
- https://ia.cr/2024/524
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}