Paper 2025/753
Linear-Time Accumulation Schemes
, New York University, École Polytechnique Fédérale de Lausanne, New York UniversityAbstract
Proof-carrying data (PCD) is a powerful cryptographic primitive for computational integrity in a distributed setting. State-of-the-art constructions of PCD are based on accumulation schemes (and, closely related, folding schemes). We present WARP, the first accumulation scheme with linear prover time and logarithmic verifier time. Our scheme is hash-based (secure in the random oracle model), plausibly post-quantum secure, and supports unbounded accumulation depth. We achieve our result by constructing an interactive oracle reduction of proximity that works with any linear code over a sufficiently large field. We take a novel approach by constructing a straightline extractor that relies on erasure correction, rather than error-tolerant decoding like prior extractors. Along the way, we introduce a variant of straightline round-by-round knowledge soundness that is compatible with our extraction strategy.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- interactive oracle reductionsaccumulation schemeslinear codes
- Contact author(s)
-
bb @ nyu edu
alessandro chiesa @ epfl ch
giacomo fenzi @ epfl ch
ww @ priv pub - History
- 2025-04-28: revised
- 2025-04-27: received
- See all versions
- Short URL
- https://ia.cr/2025/753
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/753,
author = {Benedikt Bünz and Alessandro Chiesa and Giacomo Fenzi and William Wang},
title = {Linear-Time Accumulation Schemes},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/753},
year = {2025},
url = {https://eprint.iacr.org/2025/753}
}
