Paper 2024/1606
NeutronNova: Folding everything that reduces to zero-check
Abstract
We introduce NeutronNova, a new folding scheme for the zero-check relation: an instance-witness pair is in the zero-check relation if a corresponding multivariate polynomial evaluates to zero for all inputs over a suitable Boolean hypercube. The folding scheme is a two-round protocol, and it internally invokes a \emph{single} round of the sum-check protocol. The folding scheme is more efficient than prior state-of-the-art schemes and directly benefits from recent improvements to the sum-check prover. The prover’s work is the cost to commit to a witness and field operations in a single round of the sum-check protocol. So, if the witness contains "small" field elements, the prover only commits to "small" field elements. The verifier’s work is a constant number of group scalar multiplications, field operations, and hash computations. Moreover, the folding scheme generalizes to fold multiple instances at once and requires only
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- folding schemesproof systemsincrementally verifiable computationzero-knowledge
- Contact author(s)
-
akothapalli @ berkeley edu
srinath @ microsoft com - History
- 2024-10-09: approved
- 2024-10-09: received
- See all versions
- Short URL
- https://ia.cr/2024/1606
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1606, author = {Abhiram Kothapalli and Srinath Setty}, title = {{NeutronNova}: Folding everything that reduces to zero-check}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1606}, year = {2024}, url = {https://eprint.iacr.org/2024/1606} }