A set displays a (delta, gamma)-proximity gap to a linear code, C, if either all elements are delta-close in relative Hamming distance to a codeword in C or only gamma of them are. Proximity gaps of the set A_{v,u} := {v + r u : r in F }, for fixed vectors v,u, are fundamental to the security and efficiency of an extremely efficient family of Interactive Oracle Proofs (IOPs) from FRI (ICALP 2018), where larger delta implies more efficient verifiers and smaller gamma implies more efficient provers.
Building on FRI, the authors of BaseFold (Crypto 2024) introduced a new family of IOPs with concretely faster provers. However, BaseFold additionally requires that if all elements of A_{v,u} are close to the code, then they all agree with their respective nearest codewords in a fixed, shared set of locations.
We prove this to be true for all linear codes when delta
link to paper: https://eprint.iacr.org/2024/1843.pdf
