Paper 2025/753

Linear-Time Accumulation Schemes

Benedikt Bünz, New York University
Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Giacomo Fenzi, École Polytechnique Fédérale de Lausanne
William Wang, New York University
Abstract

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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.