Welcome to the resource topic for
**2024/1512**

**Title:**

Improved Soundness Analysis of the FRI Protocol

**Authors:**
Yiwen Gao, Haibin Kan, Yuan Li

**Abstract:**

We enhance the provable soundness of FRI, an interactive oracle proof of proximity (IOPP) for Reed-Solomon codes introduced by Ben-Sasson et al. in ICALP 2018. More precisely, we prove the soundness error of FRI is less than \max\left\{O\left(\frac{1}{\eta}\cdot \frac{n}{|\mathbb{F}_q|}\right), (1-\delta)^{t}\right\}, where \delta\le 1-\sqrt{\rho}-\eta is within the Johnson bound and \mathbb{F}_q is a finite field with characteristic greater than 2. Previously, the best-known provable soundness error for FRI was \max\left\{O\left(\frac{\rho^2}{\eta^7}\cdot \frac{n^2}{|\mathbb{F}_q|}\right), (1-\delta)^{t}\right\}, as established by Ben-Sasson et al. in FOCS 2020.

We prove the number of \emph{bad} folding points in FRI is linear in the length n of codeword when it is \delta-far from the Reed-Solomon code. This implies the linear proximity gaps for Reed-Solomon codes and improves the provable soundness of batched FRI. Our results indicate that the FRI protocol can be implemented over a smaller field, thereby enhancing its efficiency. Furthermore, for a fixed finite field \mathbb{F}_q, we prove that FRI can achieve improved security.

**ePrint:**
https://eprint.iacr.org/2024/1512

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .