Paper 2024/1512
Improved Soundness Analysis of the FRI Protocol
Abstract
We enhance the provable soundness of FRI, an interactive oracle proof of proximity (IOPP) for ReedSolomon codes introduced by BenSasson 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 bestknown 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 BenSasson 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 ReedSolomon code. This implies the linear proximity gaps for ReedSolomon 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.
Metadata
 Available format(s)
  withdrawn 
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 FRI protocolReedSolomon proximity testing
 Contact author(s)

ywgao21 @ m fudan edu cn
hbkan @ fudan edu cn
yuan_li @ fudan edu cn  History
 20241002: withdrawn
 20240926: received
 See all versions
 Short URL
 https://ia.cr/2024/1512
 License

CC BY