International Association
for Cryptologic Research

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.

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.