Paper 2022/1576 Original: eprint.iacr.org/2022/1576 ↗
Folding Schemes with Selective Verification
Abstract
In settings such as delegation of computation where a prover is doing computation as a service for many verifiers, it is important to amortize the prover’s costs without increasing those of the verifier. We introduce folding schemes with selective verification. Such a scheme allows a prover to aggregate m NP statements $x_i\in \mathcal{L}$ in a single statement $x\in\mathcal{L}$. Knowledge of a witness for $x$ implies knowledge of witnesses for all $m$ statements. Furthermore, each statement can be individually verified by asserting the validity of the aggregated statement and an individual proof $\pi$ with size sublinear in the number of aggregated statements. In particular, verification of statement $x_i$ does not require reading (or even knowing) all the statements aggregated. We demonstrate natural folding schemes for various languages: inner product relations, vector and polynomial commitment openings and relaxed R1CS of NOVA. All these constructions incur a minimal overhead for the prover, comparable to simply reading the statements.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2022-11-25: last updated
- 2022-11-14: published
- Short URL
- https://ia.cr/2022/1576
- License
- https://creativecommons.org/licenses/by-nc-sa/4.0/
BibTeX
@misc{cryptoeprint:2022/1576,
author = {Carla Ràfols and Alexandros Zacharakis},
title = {Folding Schemes with Selective Verification},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/1576},
year = {2022},
url = {https://eprint.iacr.org/2022/1576}
}