An important step in the soundness analysis of the FRI-IOPP is bounding the probability of an “unlucky fold”: assuming that the prover is cheating (so that the initial oracle is -far from the code), how likely is it that the verifier “unluckily” chooses a folding challenge such that the -folding of the oracle is not -far from its code? We describe here how to bound this probability using the Correlated Agreement Theorem from [PG-RSC].
Notation
Let be a finite field and suppose is a multiplicative subgroup with even order, so that is a 2-to-1 map . Write (resp. ) for the space of all -valued functions on (resp. ). Denote by the evaluation map , and for any , write for the Reed-Solomon code consisting of evaluations of polynomials with degree less than on . Write for the relative Hamming distance.
Define by The map , which operates in the evaluation domain, corresponds to the familiar even/odd decomposition of a polynomial in the coefficient domain. In particular: and so the folding of using can be defined using via:
The “Correlated Agreement Theorem”
Let , and write for the following statement, proven in [PG-RSC] (as Theorem 4.1):
Suppose that , and that are such that Then there exists with and such that
The Correlated Agreement Theorem & Unlucky Folds
The contrapositive of can be used to bound the probability of an unlucky fold as follows.
Assume that is -far from . Then Suppose (for contradiction) that there exist and with and Set and write . Then for any and either of its two square roots : and so and agree on a subset of density Thus we would have that , which would contradict the -farness of from the code. Thus no such , and exist. Therefore, by the contrapositive of , we have that i.e. that the probability of the folding failing to be -far from (an “unlucky fold”) is strictly less than .
Proving the Correlated Agreement Theorem
The Correlated Agreement Theorem, in the case where is at most the unique decoding radius, can be proven by running the Berlekamp-Welch decoder over the function field (where , transcendental over , stands in for the folding challenge). This works since the Berlekamp-Welch decoder is really just a result from linear algebra, and so works over any field. The other ingredient is the Polishchuk-Spielman Lemma. A proof of the theorem and this lemma are given in [PG-RSC].
References
[PG-RSC]: E. Ben-Sasson, D. Carmon, Y. Ishai, S. Kopparty and S. Saraf, “Proximity Gaps for Reed–Solomon Codes,”, 2020 (pdf).