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 .