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. Bünz, 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Arc: Accumulation for Reed–Solomon Codes

  • Benedikt Bünz,
  • Pratyush Mishra,
  • Wilson Nguyen,
  • William Wang

摘要

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. Bünz, 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.