\usepackageamsmath

Unlucky folds & the correlated agreement theorem

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 αF 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 F be a finite field and suppose ΩF× is a multiplicative subgroup with even order, so that ωω2 is a 2-to-1 map ΩΩ2. Write FΩ (resp. FΩ2) for the space of all F-valued functions on Ω (resp. Ω2). Denote by EΩ the evaluation map f(f(ω))ωΩFΩ, and for any d>0, write RSd[Ω]=EΩ(F[X]<d) for the Reed-Solomon code consisting of evaluations of polynomials with degree less than d on Ω. Write Δ for the relative Hamming distance.

Define Θ=(Θ0,Θ1):FΩFΩ2×FΩ2 by (Θ0u)ω2=uω+uω2,(Θ1u)ω2=uωuω2ω,ωΩ, uFΩ. The map Θ, which operates in the evaluation domain, corresponds to the familiar even/odd decomposition of a polynomial in the coefficient domain. In particular: uω=(Θ0u)ω2+ω(Θ1u)ω2,ωΩ, uFΩ, and so the folding Ψαu of uFΩ using αF can be defined using Θ via: Ψα:FΩFΩ2,u(Θ0u)+α(Θ1u),uFΩ.

The “Correlated Agreement Theorem” CATd,Ω

Let ρ=d/|Ω|, and write CATd,Ω for the following statement, proven in [PG-RSC] (as Theorem 4.1):

Suppose that δ(0,1ρ2], and that u(0),u(1)FΩ are such that | {αF | Δ(u(0)+αu(1),RSd[Ω])<δ} ||Ω|. Then there exists ΛΩ with |Λ||Ω|1δ and f(0),f(1)F[X]<d such that f(0)(λ)=uλ(0),f(1)(λ)=uλ(1),λΛ.

The Correlated Agreement Theorem & Unlucky Folds

The contrapositive of CATd/2,Ω2 can be used to bound the probability of an unlucky fold as follows.

Assume that uFΩ is δ-far from RSd[Ω]. Then Δ(u,EΩf)δ,fF[X]<d. Suppose (for contradiction) that there exist f(0),f(1)F[X]<d/2 and ΛΩ2 with |Λ|/|Ω2|1δ and f(0)(λ)=(Θ0u)λ,f(1)(λ)=(Θ1u)λ,λΛ. Set f(X)=f(0)(X2)+f(1)(X2) and write Λ={ωΩ | ω2Λ}. Then for any λΛ and either of its two square roots ωΛ: f(ω)=f(0)(λ)+ωf(1)(λ)=(Θ0u)λ+ω(Θ1u)λ=uω, and so fF[X]<d and uFΩ agree on a subset ΛΩ of density |Λ||Ω|=|Λ||Ω2|1δ. Thus we would have that Δ(u,EΩf)<δ, which would contradict the δ-farness of u from the code. Thus no such f(0), f(1) and Λ exist. Therefore, by the contrapositive of CATd/2,Ω2, we have that | { αF | Δ(Θ0u+αΘ1u,RSd/2[Ω2])<δ } |<|Ω|. i.e. that the probability of the folding Ψαu failing to be δ-far from RSd/2[Ω2] (an “unlucky fold”) is strictly less than ϵ=|Ω||F|.

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 F(α) (where α, transcendental over F, 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).

Leave a Reply

Your email address will not be published. Required fields are marked *