Fast Reed-Solomon Interactive Oracle Proofs of Proximity学习笔记

1. 引言

Eli Ben-Sasson等人2018年论文《Fast Reed-Solomon Interactive Oracle Proofs of Proximity》。该论文又俗称FRI。Full version版见Fast Reed-Solomon interactive oracle proofs of proximity (2nd revision)，包含了详细的实现细节。

Reed-Solomon（RS）码在：

• 构建quasilinear probabilistically checkable proofs（PCPs）
• 构建具有perfect zero knowledge和polylogarithmic verifiers的interactive oracle proofs（IOPs）

中承担重要角色。而证明RS码中的membership所需的巨大具体计算复杂度是在实践中部署此类PCP/IOP系统的最大障碍之一。为此，本文为RS码提出了一种新的interactive oracle proof of proximity（IOPP），将其称为Fast RS IOPP（FRI），原因在于：

• 1）它看起来像无处不在的Fast Fourier Transform（FFT）
• 2）其Prover的计算复杂性是严格线性的，其Verifier的计算复杂性是严格logarithmic的（而FFT计算复杂度是quasi-linear的，并不是严格线性的）。

之前的RS IOPPs和PCPs of proximity（PCPPs），即使针对polynomially large query complexity，其proving time也是super-linear的。

对于block-length为 N N N的codes：

• （interactive）FRI Prover的计算复杂度 < 6 ⋅ N