Welcome to the resource topic for 2024/1810
Title:
Linear Proximity Gap for Reed-Solomon Codes within the 1.5 Johnson Bound
Authors: Yiwen Gao, Haibin Kan, Yuan Li
Abstract:We establish a linear proximity gap for Reed-Solomon (RS) codes within the one-and-a-half Johnson bound. Specifically, we investigate the proximity gap for RS codes, revealing that any affine subspace is either entirely \delta-close to an RS code or nearly all its members are \delta-far from it. When \delta is within the one-and-a-half Johnson bound, we prove an upper bound on the number of members (in the affine subspace) that are \delta-close to the RS code for the latter case. Our bound is linear in the length of codewords. In comparison, Ben-Sasson, Carmon, Ishai, Kopparty and Saraf [FOCS 2020] prove a linear bound when \delta is within the unique decoding bound and a quadratic bound when \delta is within the Johnson bound. Note that when the rate of the RS code is smaller than 0.23, the one-and-a-half Johnson bound is larger than the unique decoding bound.
Proximity gaps for Reed-Solomon (RS) codes have implications in various RS code-based protocols. In many cases, a stronger property than individual distance—known as correlated agreement—is required, i.e., functions in the affine subspace are not only \delta-close to an RS code, but also agree on the same evaluation domain. Our results support this stronger property.
ePrint: https://eprint.iacr.org/2024/1810
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 .