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

1. 引言

Eli Ben-Sasson等人2018年论文《Fast Reed-Solomon Interactive Oracle Proofs of Proximity》。该论文又俗称FRI。

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$的codes：

• （interactive）FRI Prover的计算复杂度 $<6\cdot N$；
• （interactive）FRI Verifier的计算复杂度 $\le 2\cdot \log N$；
• query复杂度为 $2\cdot \log N$；
• 具有constant soundness：即距离某code为$\delta$的words，其被拒绝的概率为 $\text{min}\{\delta \cdot (1-o(1)),{\delta }_0\}$，其中${\delta }_0$为一个主要依赖于code rate的 positive constant。