CryptoDB
Arc: Accumulation for Reed--Solomon Codes
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | Proof-Carrying Data (PCD) is a foundational tool for ensuring the correctness of incremental distributed computations that has found numerous applications in theory and practice. The state-of-the-art PCD constructions are obtained via accumulation or folding schemes. Bunz, Mishra, Nguyen, and Wang recently introduced the first hash-based accumulation scheme, which is secure in the random oracle model and instantiable with any linear error-correcting code. However, their construction only supports a bounded number of accumulation steps. We present Arc, a hash-based accumulation scheme that supports an unbounded number of accumulation steps. The core technique underlying our approach is a method for accumulating proximity claims to a Reed–Solomon code. Unlike prior work, we work in the list-decoding regime to obtain concrete efficiency improvements. We introduce the notion of Interactive Oracle Reductions (IORs) to enable a modular and simple security analysis. These extend prior notions of Reductions of Knowledge to the setting of Interactive Oracle Proofs. |
BibTeX
@inproceedings{crypto-2025-35732,
title={Arc: Accumulation for Reed--Solomon Codes},
publisher={Springer-Verlag},
author={Benedikt Bünz and Pratyush Mishra and Wilson Nguyen and William Wang},
year=2025
}