A summary on the FRI low degree test

Ulrich Hab¨ock^∗

December 17, 2024†

Abstract

This document is an informal summary on the FRI low degree test [\[BBHR18a\]](#page-20-0), \[BCI⁺20], and DEEP algebraic linking from [\[BGKS20\]](#page-21-0). Based on its most recent soundness analysis \[BCI⁺20], we discuss parameter settings for practical security levels, how FRI is turned into a polynomial commitment scheme, and the soundness of DEEP sampling in the list decoding regime. In particular, we illustrate the DEEP method applied to proving satisfiability of algebraic intermediate representations and prove a soundness error bound which slightly improves the one in [\[Sta23\]](#page-21-1).

| | | 3.5.1
66 bits of security

9 | | | | | |

| | | 3.5.2
112 bits security

9 | | | | | |

| | | 3.5.3
128 bits security

10 | | | | | |

^∗This work was supported during my employment at Horizenlabs, Inc., and Orbis Labs.

^†This updated version of the summary corrects Section 3.7 on adding zero-knowledge.

| | | 5.2.1 Extractability | | | | | |

| | | 5.3.1 Using extension fields | | | | | |

| | | 5.3.2 Increasing the number of protocol challenges | | | | | |

| | | List decoding | | | | | |

| | | A.2.1 The Sudan decoder | | | | | |

| | | A.2.2 The Guruswami-Sudan decoder | | | | | |

FRI, in full length Fast Reed-Solomon Code Interactive Oracle Proof of Proximity, is a low-degree test for functions on an FFT domain, i.e. a smooth multiplicative subgroup D of a finite field F. Given a function

FRI proves that f corresponds to a polynomial of low degree with respect to the size of D.

The oracles provided by the FRI prover are again functions on D, or a subdomain of it, and the verifier queries the values at points from their domain only. Due to the small size of D (compared to the cryptographically large sampling spaces of polynomial IOPs) the key tool for distinguishing one polynomial from another is statistical sampling. However, a statistical test can only assure proximity, which we measure by the fractional Hamming distance

In FRI the prover convinces the verifier that a given function f: D \longrightarrow F is \theta -close (and not necessarily equal) to a low-degree polynomial, i.e.

We stress that fact that this summary does not present any novelties. Instead it is an outcome of my learnings when reading the papers \[BCI+20], [\[BGKS20\]](#page-21-0), [\[BBHR18a\]](#page-20-0), [\[KPV19\]](#page-21-2) and [\[Sta23\]](#page-21-1). The document provides an overview of FRI and its soundness analysis, including some background on decoding Reed-Solomon codes. It discusses the DEEP method and how it is related to polynomial commitment schemes and we sketch the more general notion of list polynomial commitment schemes [\[KPV19\]](#page-21-2). Finally we illustrate how soundness error bounds are proven for the DEEP method in the list decoding regime. In the course the latter we clarify two points of [\[Sta23\]](#page-21-1), which are the usage of degree correction factors (these are not needed for the DEEP method), and the quadratic occurence of the decoder list size bound in their soundness error formula, which can be replaced by a linear term.

We assume that the reader knows (public-coin) interactive oracle proofs and their security notions [\[BCS16\]](#page-20-2), such as soundness, proof of knowledge, and statistical (i.e. perfect) honest verifier zero-knowledge. Any IOP with these security properties can be compiled into a succinct non-interact-ive argument of knowledge in the random oracle model [\[BCS16\]](#page-20-2): The prover oracle messages are committed by Merkle roots using the random oracle, and the verifier coins are the answers of the random oracle given the prover messages as its input.

1.1 Notation

and we shall write

for its fractional variant. Given any subset V ⊆ F ^D, we denote by

the minimal distance of f ∈ F ^D to V , and likewise we define the minimal fractional Hamming distance. We denote by

In the context of oracle proofs, we denote oracles for functions f ∈ F ^D by f , and occasionally call them domain evaluation oracles to distinguish from the oracle notion of univariate polynomial IOPs [\[BFS20\]](#page-21-3), which models an ideal polynomial commitment scheme. In order to a closer alignment with the compiled protocol in the random oracle model, we prefer to say that a party P (the prover) "sends" [f] to another party V (the verifier), meaning that P sets up the oracle for f and V obtains oracle access for it.

As in polynomial IOPs, building random linear combinations is the core reduction argument in FRI . While the soundness of it is easily proven in the polynomial model, this is not the case for domain evaluations. Even in the most elementary case, proving that if with noticeable probability a random linear combination of two given functions f_0 , f_1 is \theta -close to a Reed-Solomon codeword, i.e.

then a similar proximity would hold for f_0 and f_1 , is non-trivial, in particular when targeting only a small increase in the distance bound \theta . The most advanced result is the correlated agreement theorem (or proximity gap theorem) of Ben-Sasson, et al. [BCI⁺20]. We state it for the case of algebraic curves, which is typically favored in the context of proof composition.

for every \lambda \in F .

The proof of the correlated agreement theorem, including concrete values for the soundness error bound \varepsilon , is an algebraic analysis of the Berlekamp-Welch or the Guruswami-Sudan list decoder over the rational function field K = F(Z). It uses the Polichuk-Spielmann lemma to "glue together" the outputs of the decoder for f_0 + \lambda \cdot f_1 + \ldots + \lambda^{N-1} \cdot f_{N-1} over the "small" field F by means of the decoder result for the word

over the infinite field K: If for a noticeable fraction of \lambda 's the distance to the Reed-Solomon code is \leq \theta , then the same holds over F(Z).

Depending on the decoding regime the following values for \varepsilon are obtained by [BCI⁺20]:

1. Unique decoding regime. For \theta \in \left(0, \frac{1-\rho}{2}\right] , Theorem 1 holds with

1. List decoding regime. For \theta \in \left(\frac{1-\rho}{2}, 1-\sqrt{\rho}\right) and setting \theta = 1-\sqrt{\rho} \cdot \left(1+\frac{1}{2m}\right) , with m \geq 3 , Theorem 1 holds with

(2)

For linear varieties of the form f_0 + \lambda_1 \cdot f_1 + \ldots + \lambda_{N-1} \cdot f_{N-1} a similar result holds, with the (N-1)-term in (1) and (2) replaced by 1. See the full version of [BCI⁺20], Theorem 4.1 and 5.1.

given a proximity parameter θ of at most the Johnson list decoding bound. As most interactive oracle proofs, the FRI protocol is comprised of a commit phase and a query phase. The commit phase consists of one or several rounds, in which the prover sends domain evaluation oracles to the verifier, who then responds with a random challenge. That phase of FRI performs a random reduction similar to the one of an inner product argument \[BCC+16], at least halving the instance size with each step by a linear folding procedure. In the concluding query phase, the verifier asks for openings of the oracles at random points from their domain of definition. These openings are then used to check consistency of each reduction step of the commit phase.

The commit phase of FRI starts with the instance to proven, i.e. the polynomial p0(X) = p(X) and its domain evaluation over D⁰ = D. This instance is stepwised reduced by means of a random folding procedure, yielding a sequence of polynomials

as words over the domains

respectively, wheras their degree bounds kⁱ , deg pi(X) < kⁱ , decrease with the same ratio as the domains. The quotients

• In each round i, 1 ≤ i ≤ r, the prover decomposes the previous polynomial pi−1(X) of deg pi−1(X) < ki−1, according to

p_{i-1}(X) = F_0(X^{a_i}) + X \cdot F_1(X^{a_i}) + \dots + X^{a_{i-1}} \cdot F_{a_i-1}(X^{a_i}), \tag{3}

where each

(For aⁱ = 2 this is the decomposition into odd and even parts.) The verifier samples a random challenge λⁱ ←\$ F, sends it to the prover, which in turn responds with the linear combination

Let us elaborate on the decomposition (3) in terms of the reduction map

Notice that for each y in D_i , y = x^{a_i} , the values of F_0(y), \ldots, F_{a_i-1}(y) are uniquely determined by the values of

on the coset \pi_i^{-1}(y) = x \cdot \ker(\pi_i) , and these values are exactly the ones given by p_{i-1}(X) . Hence if \tau is a generator of \ker(\pi_i) = \{1, \tau, \dots, \tau^{a_i-1}\} , then

where (L_0, ..., L_{a_i-1}) is the Lagrange interpolation map for the coset x \cdot ker(\pi_i) . In other words,

p_i(\pi_i(x)) = \mathsf{FFT}_{\lambda_i/x} \left( p_{i-1} \left( \tau^0 \cdot x \right), \dots, p_{i-1} \left( \tau^{a_i-1} \cdot x \right) \right), \tag{4}

that is the Fourier transform of the vector (p_{i-1}(\tau^0 \cdot x), \dots, p_{i-1}(\tau^{a_i-1} \cdot x)) , evaluated at \frac{\lambda_i}{x} . This equation will be used to check consistency between the provided oracles.

In some situations it is more efficient to compute the values of p_i(y) over D_i directly from the ones of p_{i-1}(x) , x \in D_{i-1} , using (4). In terms of field additions A, multiplications M, and FFT operations \mathsf{FFT}(a_i) of size a_i , this can be done¹ in

compared to

when computing the domain evaluation of the random linear combination p_i(X) . Hence using equation (4) is more efficient whenever

3.2 Sampling phase

In the query phase the verifier samples at random points from the defining domains of the oracles, and use the returned values to check the consistency of all reduction steps.

Protocol 2 (FRI query phase). The query phase consists of s \ge 1 many rounds.

• In each round the verifier samples an x⁰ ∈ D⁰ uniformly at random, computes x1, . . . , x^r recursively via xⁱ = πi(xi−1), and checks if

for every i = 1, . . . , r, by querying the values of each pi−¹ over the coset xi−¹ · ker πi.

Notice that unlike in \[BCI+20] we choose x⁰ uniformly from D0, and form the xⁱ by projecting xi−¹ onto Dⁱ . In distribution, this way of sampling is equivalent to the one in the paper, which starts with x^r ←\$ Dr, and then samples xi−¹ uniformly from the coset π −1 i (xi).

3.3 Batching

As for linear polynomial commitment schemes, batching is done via random linear combinations. We will only discuss the algebraic variant, which uses powers of a single random challenge. (Again, this is the one favored in the context of proof composition.)

Given a batch of L low-degree polynomials q0(X), . . . , qL−1(X), the verifier samples a random challenge λ ←\$ F. The prover computes the linear combination

h(X) = \sum_{i=0}^{L-1} \lambda^i \cdot q_i(X), \tag{6}

sends the oracle of it,

to the verifier. Then both prover and verifier continue with FRI for h. Each x⁰ ←\$ D⁰ = D from the query phase of FRI is used to additionally check consistency between the oracle for h(X) and the ones in the batch, q0(X), . . . , qL−1(X), using \(6\).

3.4 Soundness

The soundness analysis of FRI is based on a strengthening of the correlated agreement theorem, which allows to additionally keep track of the success probability for the FRI query phase by a sub-probability measure µ. We state that weighted correlated agreement theorem in Appendix A.3. For proximity parameters close to the Johnson bound, the soundness error of the batched FRI oracle proof is as follows2 :

Theorem 2 (Batched FRI soundness error, full version of \[BCI+20], Theorem 8.3). Suppose that qⁱ ∈ F D, i = 0, . . . , L − 1, is a batch of functions given by their domain evaluation oracles. If an adversary passes batched FRI for RSk[F, D] and proximity parameter θ = 1− ^√ρ · 1 + ¹ 2m , m ≥ 3, with a probability larger than

(7)

then the functions qⁱ ∈ F ^D, i = 0, . . . , L − 1, have correlated agreement with RSk[D, F] on a set of density of at least α > 1 + ¹ 2m · ^√ρ.

²We would like to thank Paul Gafni for pointing out a typo in formula \(7\) in a previous version of the document.

Remark 3. The case of linear batching of two functions q_0 , q_1 corresponds to the case L=2, in which L-\frac{1}{2}=\frac{3}{2} . The same is true for affine batching of several functions, its soundness error is obtained from (7) by replacing L-\frac{1}{2} by \frac{3}{2} , see [BCI⁺20].

The first two terms in (7),

correspond to soundness error of the commit phase, reflecting the systematic error estimated by the correlated agreement theorem and collected over the batching step and the reduction rounds. In words, if the oracles in the batch do not share the claimed correlated agreement for \alpha = 1 - \theta , then except with probability \varepsilon_C , the oracles produced during the commit phase cannot be "nice". That is, the set where all consistency checks would hold is at most of density \alpha . The remaining term,

is the soundness error of the query phase with s rounds. This is the probability not to detect such a set of non-"nice" oracles using s independent samples.

3.5 Example parameters

One way to settle the parameters is as follows. For target security level 2^{-\lambda} , we assure that

1. the soundness error for the commit phase is bounded by \frac{1}{2} \cdot 2^{-\lambda} . For that we choose the maximum Johnson proximity m \geq 3 so that

1. the soundness error of the query phase is bounded by \frac{1}{2} \cdot 2^{-\lambda} . Using m from the first step, we determine the number s of query rounds via

polynomials, each group committed by a single tree using Merkle caps. The height for the Merkle caps is chosen to minimize the proof size. For each blow-up factor we compute the proof size (assuming a hash size of 256 bits), and as a very coarse measure for the prover complexity the number hashes⁴it needs to compute.

^&lt;sup>3In a previous version of the document the example parameters where based on linear batching of FRI. The current ones consider algebraic batching.

^&lt;sup>4Each call of the hash processes another r = 256 bits.

3.5.1 66 bits of security

Such a configuration might be still interesting in practice, as its security can be increased by grinding (see [\[Sta23\]](#page-21-1)): Another 14 bits proof of work bound to the proof generation, and one obtains overall 80 bits of security.

• With a degree 2 extension of Fb, hence a field size of 128 bits, the best security level one can obtain for ρ = 2−⁵ is about 69 bits. The commit phase error is

\varepsilon_C \approx 2^{-67.21} ,

with Johnson proximity m = 3. To have about the same soundness error in the query phase, we demand s = 29 samples, yielding

\varepsilon_Q \approx 2^{-68.33} .

With a reduction strategy {a1, a2} = {2 4 , 2 ³} we obtain proof sizes of about 104 kB.

• With a degree 3 extension of Fb, hence a field size of 192 bits, one can choose higher blow-up factors. For ρ = 2−⁶ we obtain 67 bits security by

\varepsilon_C \approx 2^{-67.00} ,

where the Johnson proximity is m = 1, 427. To have about the same soundness error in the query phase, we need only s = 23 samples, yielding

\varepsilon_Q \approx 2^{-68.99} .

With the same reduction strategy as before, we reduce the proof size down to 89 kB. However, this comes at the cost of about tripling the prover cost.

3.5.2 112 bits security

As in the previous setting, we discuss this level of security as it can be improved by grinding, typically up to 128 bits. All configurations use degree 3 extensions of Fb.

For higher blow-up factors, one needs to increase grinding. For example, for − log² (ρ) = 11 the best level of security that can be obtained with degree 3 extensions is 109 bits, leaving 19 bits for grinding. The proof size decreases down to 88.2 kB, at the prover cost of 6, 684, 672 hashes.

3.5.3 128 bits security

These configurations do not use grinding, and hence have quite large proof sizes. Again, we use degree 3 extensions of Fb.

3.6 Conjectured security

In their line of work on FRI \[BBHR18a, BGKS20, BCI+20] the authors make several conjectures on the soundness of FRI for proximity parameters above the Johnson bound. In the most recent one, they state the following.

Conjecture 1 (Full version of \[BCI+20], Conjecture 8.4). There exist constants c1, c² such that for all θ = 1 − ρ − η, η > 0, the soundness error in the correlated agreement theorem on f0, . . . , fN−¹ is bounded by

Remark 4. For purely linear batching, a similar conjecture is stated.

We point out that the above conjecture (as well as its corresponding one in [\[BBHR18a\]](#page-20-0)) is stated isolated from any general conjectured properties on Reed-Solomon codes, such as list decodability up to capacity bound (as done for DEEP method, see Section 5.4\). Instead it is rather justified by "[to the best of our knowledge...] nothing seems to contradict" . The authors consider the choice of c¹ = c² = 2 reasonable, and for fields of characteristic q > n they estimate that c¹ = c² = 1.

The c¹ = c² = 1 assumption is of particular interest for practitioners, as it yields proofs of halve the size as in the c¹ = c² = 2 case. For example, it is used by the ethSTARK [\[Sta23\]](#page-21-1) (besides its provably secure parameter setting), as well as by Plonky2 [\[Pol\]](#page-21-4).

3.7 Adding zero-knowledge

Zero-knowledge for FRI has to be provided on application level. In our use cases, the witnesses of an argument correspond to the values of some polynomial q(X) on a given domain H (the proving domain for Plonk, say). To protect it from being leaked by the queries of the s query rounds (as well as by the final reduction polynomial), one uses a an H-disjoint coset a · D of the FRI domain, and randomizes q(X) outside the domain H. That is, the batching and the entire FRI reduction takes place on

instead of D⁰ ⊇ D¹ ⊇ . . . ⊆ Dr, where (a · D0) ∩ H = ∅. This leads to running batched FRI for qi(X), i = 0, . . . , L − 1, over the non-shifted domain D⁰ on the shifted polynomials

i = 0, . . . , L − 1, instead.

The concrete degree of freedom in the randomization of the polynomials depends on the number of FRI queries and the degree of the extension they are taken from, as well as the the polynomial IOP on top of FRI. Furthermore, and unlike described in a previous version of the survey, it is crucial to add a separate blinding polynomial h(x) to the batch, in order to assure that no information is revealed by the folding oracles of FRI. We refer to [HK24] for a detailed description of the [BCR⁺19] randomization of FRI, plus additional subtleties one has to take care of in the context of the complete IOP of the STARK.

FRI can be turned into a polynomial commitment scheme by means of the evaluation quotients

of a committed word f \in F^D . This approach, called the DEEP method in [BGKS20] corresponds to the algebraic linking of the evaluation identity

with a low-degree problem on the sampling domain D, assuming that z \notin D . (For z \in D the oracle can directly answer with the queried value. We will omit this case throughout our discussion.)

For proximity parameters \theta up to the unique decoding radius one obtains a polynomial commitment scheme in the classical sense (when compiling the oracle proof into an argument using a secure partially disclosable vector commitment). In the list decoding regime the situation is a bit more subtle due to the non-uniqueness of \theta -close code words. In this case the DEEP method can be viewed as an oracle proof for a more general type of polynomial commitment scheme, called list polynomial commitment scheme in [KPV19]. However, as their notion does not cover the power of correlated agreement, we shall only sketch list polynomial commitment schemes.

4.1 In the unique decoding regime

For a proximity bound up to the unique decoding radius, i.e. \theta < \frac{1-\rho}{2} , the situation is quite simple. However, there are several ways to algebraically link the evaluation identity with a low-degree test.

4.1.1 A first construction

We first discuss a naive scheme, in which the maximum degree corresponds to the degree proven by FRI.

• Setup: The maximum degree d = k 1 is chosen as the maximum degree of polynomials belonging to \mathsf{RS}_k[F,D] .
• Commit: Given a polynomial p(X) of degree \deg p(X) \leq d , the prover commits its domain evaluation over D, i.e.

• Evaluation proof: Given an opening claim (z, v) with z \notin D , the prover engages with the verifier in a batched FRI argument on

f_2(x) = x \cdot f_1(x) = x \cdot \frac{p(x) - v}{x - z}.

with proximity bound \theta = \frac{1-\rho}{2} . This proof batches the functions into a random linear combination f_1(x) + \lambda \cdot f_2(x) = (1 + \lambda \cdot x) \cdot \frac{p(x) - v}{x - z} , and then runs FRI on it. The linear term \lambda \cdot x is called degree correction factor.

We point out that the two functions f_1 , f_2 are not needed to be provided by another oracle, as their evaluations on D can be computed from the values of p(x).

which evaluates to v at z. Notice that \delta(p(x), P(X)) < \frac{1-\rho}{2} , hence a single evaluation proof implies distance to a degree \leq d polynomial of at most the unique decoding radius. As a consequence, any other evaluation proof (on the same or any other query) is consistent with that unique degree \leq d polynomial, showing that we indeed have a polynomial commitment scheme.

4.1.2 The refined scheme

By similar reasoning (based on a degree k=d+1 polynomial vanishing on a set of density > \rho ) we can remove the degree correction factor in the above naive scheme, running FRI for a proximity parameter \theta < \frac{1-\rho}{2} , only on the evaluation quotient of the claim: For any two evaluation claims (z_1, v_1) and (z_2, v_2) we conclude the existence of polynomials p_1(X) , p_2(X) of degree \leq k-1 and sets A_1 , A_2 of density 1-\theta > \frac{1+\rho}{2} such that

v_2 + (X - z_2) \cdot p_2(X),

agree with p(x) on A_1 and A_2 , respectively. Since the density of A_1 \cap A_2 is at least 1 - 2 \cdot \theta > \rho , it contains at least k + 1 points, and by degree we may conclude the formal identity

This leads to the following optimized scheme:

• Setup: The maximum degree is d^+ = k , where k is the absolute rate of \mathsf{RS}_k[F,D] .
• Commit: Given a polynomial p(X) of degree \deg p(X) \leq d^+ , the prover commits its domain evaluation over D, i.e.

• Evaluation proof: Given an opening claim (z, v) with z \notin D , the prover engages with the verifier in a batched FRI argument on

with proximity bound \theta < \frac{1-\rho}{2} .

4.1.3 Multi-point queries

Instead of batching several point evaluation quotients, queries for the values of a polynomial p(X) over a small set \Omega = \{z_1, ..., z_m\} \subset F \setminus D can be also proven via the multi-evaluation identity

\sum_{i=1}^{m} (p(X) - v_i) \cdot L(z_i, X) = 0 \mod v_{\Omega}(X), (8)

where v_{\Omega}(X) = \prod_{j=1}^{m} (X - z_j) is the vanishing polynomial of \Omega and L(z_i, X) = \prod_{j \neq i} \frac{X - z_j}{z_i - z_j} is the Lagrange polynomial at z_i . Similar to the single query case, one argues using the quotient

h(x) = \text{Quotient}(p, \{(z_i, v_i) : i = 1, \dots, m\}) = \frac{p(x) - V(x)}{v_{\Omega}(x)}, (9)

where

is the unique degree \leq m-1 polynomial that interpolates the claim.

Alternatively, as in the batch evaluation protocol of Boneh, et al. [BDFG21], one can replace the Lagrange kernel with the non-normalized variant D(z_i, X) = \prod_{j \neq i} (X - z_j)

and work with the quotient

instead.

In both cases one has to limit the number m of simultaneous queries to some maximum value m_{max} , satisfying

For this it is sufficient to choose k + m_{max} \le (1 - \theta_0) \cdot n = \frac{k+n}{2} , and hence m_{max} \le \frac{n-k}{2} . Even with the lowest blow-up factor we have n \ge 2 \cdot k , it is thus enough to demand

In our applications the bound on m_{max} is trivially met, as only few values are queried in the run of the proof. Furthermore, given a polynomial we use multi-point queries of fixed given size m \leq m_{max} . As a consequence the maximum degree in the setup can be enlarged to d_{max} = k + m - 1 .

4.2 List commitments

In the list decoding regime the situation is a bit more subtle. Running FRI for \mathsf{RS}_k[F,D] with a proximity parameter \frac{1-\rho}{2} < \theta < 1 - \sqrt{\rho} on an evaluation quotient

only proves agreement of p with an evaluation-claim-consistent polynomial of degree d^+ = k on a set of density greater than \alpha = 1 - \theta . This might be not large enough for proving the polynomials of different runs

such code words. This leads to the idea of list polynomial commitment schemes as in [KPV19] with the following information-theoretic model: The prover sets up an oracle which contains a list of l, 1 \le l \le L , low-degree polynomials, and the oracle is allowed to choose which one to evaluate on a given query. Such extended notion is practical as security proofs in the oracle model are similar to polynomial oracle proofs. However, the notion of list polynomial oracles as given in [KPV19] is not strong enough to capture correlated agreement, and as a consequence soundness error bounds are too coarse. For this reason we do not dive into formal details of that model, and instead directly work with DEEP algebraic linking.

In this section we discuss the DEEP algebraic linking (DEEP-ALI) [BGKS20] and demonstrate its application to proving satisfiability of algebraic intermediate representations (AIR). Other representations such as randomized AIR or Plonk [GWC19] can be treated similarly.

5.1 Algebraic linking and the DEEP method

Algebraic linking transforms satisfiability of algebraic identities over algebraic subsets of F into proximity problems of low-degree extensions to Reed-Solomon codes over "outside" domains (i.e. disjoint to the algebraic subset). A family of functions g_1, \ldots, g_N on \Omega = \{x_1, ..., x_n\} satisfies an algebraic identity

on \Omega (P is a polynomial), if and only if their low-degree extensions p_1(X), \ldots, p_N(X) satisfy that P(X, p_1(X), \ldots, p_N(X)) is divisible by the vanishing polynomial v_{\Omega}(X) = \prod_{i=1}^n (X - x_i) of \Omega , i.e. the quotient

is a low-degree polynomial. This divisibility criterion is translated to the proximity of given code words

(the honest prover chooses the domain evaluations of p_1(X), \ldots, p_N(X) and h(X) over D) to low-degree polynomials, i.e. a Reed-Solomon code words⁵. For this the proximity parameter needs to be chosen so that the agreement sets are large enough to infer from local satisfiability of algebraic identities to their satisfiability over the entire field F. This means that the sampling domain D is such that the notion of low-degree is determined by the degree of P(X, p_1(X), ..., p_N(X)) . DEEP-ALI instead allows for decoupling the sampling domain size from the degree of P.

DEEP-ALI is very much in alignment with a polynomial IOP for proving that

P(X, p_1(X), ..., p_N(X)) = h(X) \cdot v_{\Omega}(X). (12)

^&lt;sup>5In the case of a single batched FRI proof for the f_i together with h, one needs to use degree correction factors as in Section 4.1.1.

Instead of showing proximity of the quotient

to a low-degree polynomial, one samples a random point z ←\$ F outside the domain D, and let the prover provide evaluations claims vⁱ , i = 1, . . . , w for pⁱ , and v for h, which are used to check the identity \(12\) at X = z. The validity of the values are supported by proving proximity of the point evaluation quotients

as well as

one can even use a sampling domain the size of which is not determined by the degree of h(X). (We use a different decomposition as in \[BGKS20, [Sta23\]](#page-21-1), which does not imply any further constraints on the sampling space for z.)

In the unique decoding regime, the DEEP-ALI approach is equivalent to a (univariate) polynomial IOP using FRI as a polynomial commitment scheme as described in Chapter 4. For larger proximity parameters, one can generalize the polynomial oracle model to list polynomial commitment schemes as done in [\[KPV19\]](#page-21-2), but their approach does not yield soundness bounds which are as tight as given by the correlated agreement theorem. In order not to introduce yet another oracle model which reflects this specific correlated agreement property of batched FRI, we directly show how to apply the DEEP method to proving satisfiability of an algebraic intermediate representation.

5.2 DEEP-ALI of an AIR

An algebraic intermediate representation (AIR), see \[BBHR18b, BGKS20, [Sta23\]](#page-21-1), is defined over an FFT domain H ⊂ F with generator g. Each x in H carries a "row" of w witnesses (or, "columns")

on which a certain number of algebraic constraints are imposed. For simplicity we restrict ourselves to constraints between neigboring rows only, i.e. polynomials

each Pⁱ being imposed on a specified coset aⁱ · Hⁱ ⊆ H, where Hⁱ is a subgroup of H. Hence satisfiability of the AIR is defined by

P_i(x, g_1(x), \dots, g_w(x), g_1(g \cdot x), \dots, g_w(g \cdot x)) = 0 \quad \forall x \in a_i \cdot H_i,

for every i = 1, . . . , C. In terms of polynomials p1(X), . . . , pw(X) ∈ F[X] extending the witness functions g1, . . . , gw, satisfiability of an AIR constraint Pⁱ on aⁱ · Hⁱ can be expressed by demanding the quotient

s_i(X) \cdot P_i(p_1(X), \dots, p_w(X), p_1(g \cdot X), \dots, p_1(g \cdot X)) = 0 \mod v_H(X), (15)

where

s_i(X) = \frac{v_H(X)}{v_{a_i \cdot H_i}(X)} \in F[X]

is the selector polynomial⁶ for the constraint P_i . The overall degree of the AIR is defined as

where deg(P_i) is the total degree of P_i .

However, the agreement parameter used for FRI is taken slightly larger than \alpha = \left(1 + \frac{1}{2m}\right) \cdot \sqrt{\rho}, m \ge 3 , namely

where

The DEEP-ALI protocol (for simplicity without zero-knowledge) for our AIR is as follows:

• 1. The prover sends the domain evaluation oracles [p_1], \ldots, [p_w] for p_1(X), \ldots, p_w(X) to the verifier, who responds with a randomness \lambda \leftarrow F .

$$\sum_{i=1}^{C} \lambda^{i-1} \cdot s_i(X) \cdot P_i(p_1(X), \dots, p_w(X), p_1(gX), \dots, p_w(gX))

(21)

The verifier answers with a DEEP query, i.e. a random z ←\$ F \ (D ∪ H).

• 3. Upon receiving the DEEP query z, the prover sends the evaluation claims (z, vi,1), (g · z, vi,2), i = 1, ..., w, for the witness polynomials pi(X), and (z, v^j ), j = 0, ..., d − 1, for the segment polynomials hλ,j (X), to the verifier.
• 4. Eventually, prover and verifier run batched FRI for proximity of the evaluation quotients

where Vi(x) is determined from the evaluation claims as described in Section 4.1.3, i = 1, . . . , w, and

j = 0, .., d − 1, to RSk[F, D], where the chosen agreement parameter is α ⁺ as defined above. If FRI passes, and if the evaluation claims satisfy the overall identity \(21\) at X = z, the verifier accepts. (Otherwise, it rejects.)

Remark 5. Notice that the polynomial si(X) can only be succinctly evaluated outside H. For this reason that H is excluded from the sampling space of z.

Remark 6. As discussed above, our definition of AIR is equivalent to the one from \[BBHR18b, BGKS20, [Sta23\]](#page-21-1) (besides that we restricted to constraints between neighboring rows in order to keep the presentation simple). In particular the quotient polynomial hλ(X) in our protocol is the same as

which is the batched rational function used in their line of work.

Remark 7. Let us point us the difference of Protocol 3 to the IOP given in [\[Sta23\]](#page-21-1). Instead of using a purely linear batching strategy, we use the powers of a single randomness λ, which is the favoured choice in the context of proof composition. Secondly, as in [\[BGKS20\]](#page-21-0) we use multi-point quotients for the witness polynomials which are queried at z and gz. This reduces the number of polynomials on which FRI is applied, at the cost of only a slight increase in the choice of k ⁺. Thirdly, the way we decompose hλ(X) into segment polynomials \(13\) does not further reduce the sampling space for z, as is needed when using a FRI-like decomposition.

We finally state the soundness error of Protocol 3 in the oracle model.

Theorem 8 (DEEP-ALI soundness). The above oracle proof for AIR satisfiability has soundness error

with k^+ = k + 2 , L^+ = \frac{m + \frac{1}{2}}{\sqrt{\rho^+}} , \rho^+ = \frac{k^+}{n} , and \varepsilon_{FRI} being the soundness error for batched FRI for \alpha^+ -agreement with RS_k[F,D] , Theorem 2.

Remark 10. In the soundness error formula in [BGKS20], Theorem 15, the list bound L^+ occurs quadratically. This is due to the application of two separate FRI arguments, one for the batched quotients of the witness polynomials, and another one for the overall quotient polynomial. (However, the splitting technique for h is outlined in Section 5.5. therein.) For the same reason, the notion of list polynomial commitment schemes from [KPV19] would lead to the w-th power of L^+ , w being the number of witness columns. This might be acceptable for proving soundness of standard Plonk in the list polynomial oracle model, but not for a larger number of witness columns.

(Otherwise \Pr[P^ \text{ succeeds }] \leq 1 \cdot \varepsilon_1 + (\varepsilon_2 + \varepsilon_3) \cdot (1 - \varepsilon_1) < \varepsilon_1 + \varepsilon_2 + \varepsilon_3 .) Likewise, for every such "good" \lambda (by the definition of \varepsilon_1 , there are at least L^+ \cdot C many) there exists a second message of P^ , i.e. words h_{\lambda,0}, \ldots, h_{\lambda,d-1} on D such that

For each such "good" z \in F \setminus (D \cup H) (by the definition of \varepsilon_2 , there are more than L^+ \cdot (d \cdot (k^+ - 1) + (k - 1)) many) the evaluation claims pass the verifier checks, and moreover the soundness of FRI enforces the evaluation quotients

In what follows we shall call an element (P_0(X), \ldots, P_{l-1}(X)) from F[X]^l , with component polynomials of degree \leq k^+ - 1 , having correlated agreement with a vector of functions (\phi_0(x), \ldots, \phi_{l-1}(x)) on a set of density \geq \alpha^+ , an \alpha^+ -configuration for that vector of functions. Another way to express this, is that

belonging to the Reed-Solomon code \mathsf{RS}_{k^+}[K,D] over the rational function field K=F(Z) is (1-\alpha^+) -close to the K-valued function \phi(x) = \sum_{i=0}^{l-1} \phi_i(X) \cdot Z^i . Note that since \alpha^+ > \sqrt{\rho^+} , the Guruswami-Sudan list size bound (over general fields, see Appendix A.2) is applicable to \mathsf{RS}_{k^+}[K,D] . In particular, there are at most

\alpha^+ -configurations for (\phi_0(x), \dots, \phi_{l-1}(x)) .

Let us keep a combination of "good" first and second messages (f_1, \ldots, f_w) , (h_{\lambda,0}, \ldots, h_{\lambda,d-1}) fixed. We have seen above that the existence of a single "good" z implies the existence of an \alpha^+ -configuration for (f_1, \ldots, f_w, h_{\lambda,0}, \ldots, h_{\lambda,d-1}) . By the Guruswami-Sudan list size bound for \mathsf{RS}_{k^+}(K,D) (see Appendix A.2) there are at most L^+ such \alpha^+ -configurations. However, since there are more than L^+ ( d \cdot (k^+ - 1) + (k - 1) ) many "good" z, and each establishes an \alpha^+ -configuration which smoreover evaluates to the claimed values, we conclude from the pigeon-hole principle that there is at least one \alpha^+ -configuration,

for which the overall identity (21) (taking the q_{\lambda,j} as h_{\lambda,j} therein) holds at more than d \cdot (k^+ - 1) + (k - 1) many z. By the degree of the identity, this configuration is a solution of it, hence (p_1, \ldots, p_w) \in F[X]^w is an \alpha^+ -configuration for (f_1, \ldots, f_w) which satisfies

\sum_{i=1}^{C} \lambda^{i-1} \cdot s_i(X) \cdot P_i(p_1(X), \dots, p_w(X), p_1(gX), \dots, p_w(gX)) = 0 \mod v_H(X). (23)

Now let us keep a "good" first message (f_1, \ldots, f_w) fixed. We have seen that for each "good" \lambda there exists an \alpha^+ -configuration for (f_1, \ldots, f_w) which is a solution of (23). Again, by the Guruswami-Sudan list size bound for \mathsf{RS}_{k^+}[K,D] , there can be at most L^+ many w-configurations. Since there are at least L^+ \cdot C many "good" \lambda , we conclude again from the pigeon-hole principle that there is at least one \alpha^+ -configuration, which we again denote by (p_1,\ldots,p_w) , for which there are at least C many "good" \lambda for which (23) holds. By linear algebra (the Vandermonde matrix is invertible) we conclude that this configuration satisfies

for every i=1,\ldots,C . The values of (p_1,\ldots,p_w) over H satisfy the constraints the AIR. This completes the proof.

We note that in Equation (22), the term in the brackets is exactly the soundness error bound of the protocol in the (univariate) polynomial IOP model [BFS20]. As soundness in this model is essentially based on the Schwartz-Zippel lemma, we believe that the blow-up by the factor L^+ holds in general for every (public coin) polynomial IOP when replacing polynomial oracles by domain-evaluation oracles. (At least for the polynomial IOPs we know, such as [GWC19, MBKM19, CHM ^+ 20] or [HGdB21], this is the case.) Such a general transformation of (univariate) polynomial IOPs into ordinary (i.e. domain-evaluation) IOPs would be of interest, as the polynomial IOP model is widely used by practicioners. The protocol design as well as its security analysis is much easier to understand in the polynomial oracle model, and their soundness error bounds could be easily taken over. We plan to elaborate on this in a separate document.

5.2.1 Extractability

We only provide a brief sketch how to build the extractor in the oracle model, given a prover P^* which succeeds with a probability of that exceeds the soundness error bound from Theorem 8:

• 1. Sample a "good" first message [f_1], \ldots, [f_w] on which the prover succeeds with a probability greater than the soundness error bound from Theorem 8.
• 2. In this step we build a straight-line extractor from the "good" first message [f_1], \ldots, [f_w] pbtained in Step (1): Read f_1, \ldots, f_w from the oracles. By the proof of Theorem 8, (f_1, \ldots, f_w) agrees with an AIR solution (p_1(X), \ldots, p_w(X)) \in F[X]^w on a set A of density \geq \alpha^+ . To obtain this solution, one repeatedly applies the Guruswami-Sudan list decoder⁷and "intersects" their outputs as described in [Sta23], Section 5.5. One of the resulting configurations must be the one that satisfies the AIR.

5.3 Boosting soundness

In this section we outline standard techniques to lower the DEEP-ALI soundness error for AIRs over small fields F. (See [Sta23], or [?].)

5.3.1 Using extension fields

5.3.2 Increasing the number of protocol challenges

Instead of drawing protocol challenges from an extension field, one may repeatedly sample a challenge and run the remaining protocol for them in parallel. For instance, the first verifier challenge \lambda can be sampled N_1 times, \lambda_1, \ldots, \lambda_{N_1} \leftarrow F , and prove the overall polynomial identity (21) for all of these cases. This yields a lowered soundness error bound of the first round,

and increases only the number of h_{\lambda,j} polynomials (by the factor N_{\lambda} ) that are subject to the DEEP queries in the second round. Likewise, one may also take several DEEP queries z_1, \ldots, z_{N_z} from F \setminus D , and apply FRI to the batch of all resulting quotients, lowering the soundness error bound of the second round to

However, this comes at the cost of increasing the entire batch for FRI by the factor N_z (which might be acceptable in some applications, though). On the contrary, resampling of FRI challenges would increase the proof size too much. Hence for FRI extension field sampling is preferable.

^&lt;sup>7Alternatively one could run the Guruswami-Sudan list decoder over K = F(Z). However, its run-time analysis in the number of operations over F is probably more difficult.

5.4 Beyond the Johnson bound?

The conjectured soundness error for FRI alone (Conjecture 1) is not good enough to argue the security of DEEP-ALI beyond the Guruswami-Sudan list decoding bound. For that reason we also cite a general conjecture on the list decodability of Reed-Solomon codes, which is used by Ben-Sasson et al. to conjecture the soundness error of DEEP-FRI up to capacity bound.

Remark 11. No concrete assumptions on the constant C_{\rho} are made in [BGKS20].

However, practitioners seem to avoid this conjecture. The ethSTARK documentation [Sta23] takes a toy protocol as a representative for the entire DEEP-ALI of AIR, whereas the Plonky2 writeup [?] only sketches soundness in the polynomial oracle model, with no reference to list bounds.

• [BBHR18a] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon interactive oracle proofs of proximity. In ICALP 2018, 2018. Full paper: https://eccc.weizmann.ac.il/report/2017/134/.
• [BBHR18b] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. In IACR ePrint Archive 2018/046, 2018. https://eprint.iacr.org/2018/046.
• [BCC⁺16] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In M. Fischlin and J.S. Coron, editors, EUROCRYPT 2016, volume 9666 of LNCS. Springer, 2016. Full paper: https://eprint.iacr.org/2016/263.
• [BCI⁺20] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity gaps for Reed-Solomon codes. In FOCS 2020, 2020. Full paper: https://eprint.iacr.org/2020/654.
• [BCR⁺19] Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent succinct arguments for R1CS. In Y. Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, volume 11476 of LNCS. Springer, 2019.
• [BCS16] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In TCC 2016, pages 31–60, 2016.

• [BDFG21] Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon. Halo Infinite: Recursive zk-snarks from additive polynomial commitments. In CRYPTO 2021, volume 12825 of LNCS. Springer, 2021. Full paper: .
• [BFS20] Benedikt B¨unz, Ben Fisch, and Alan Szepieniec. Transparent SNARKs from DARK compilers. In EUROCRYPT 2020, 2020. Full paper: .
• [BGKS20] Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling outside the box improves soundness. In ITCS 2020, 2020. Full paper: https://eprint.iacr. org/2019/336.
• [CHM+20] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas Ward. Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In EUROCRYPT 2020, volume 12105 of LNCS, 2020. Full paper: .
• [GS99] Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometry codes. In IEEE Trans. on Information Theory, volume 45(6), 1999.
• [Gur07] Venkatesan Guruswami. Algorithmic results in list decoding. In Foundation and Trands in Theoretical Computer Science, volume 2(2), 2007.
• [GWC19] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for oecumenical non-interactive arguments of knowledge. In IACR ePrint Archive 2019/953, 2019. .
• [HGdB21] Ulrich Hab¨ock, Alberto Garoffolo, and Daniele di Benedetto. Darlin: Recursive proofs based on Marlin. In IACR preprint archive 2021/930, 2021. .
• [HK24] Ulrich Hab¨ock and Al Kindi. A note on adding zero-knowledge to STARKs. In IACR ePrint Archive 2024/1037, 2024. .
• [KPV19] Assimakis Kattis, Konstantin Panarin, and Alaxander Vlasov. REDSHIFT: Transparent snarks from list polynomial commitment IOPs. In IACR preprint archive 2019/1400, 2019. .
• [MBKM19] Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In ACM SIGSAC Conference on Computer and Communication Security, pages 2111–2128, 2019. Full paper: .
• [Pol] Polygon Labs / Polygon Zero. Plonky2: Fast recursive arguments with PLONK and FRI. .
• [Sta23] StarkWare Team. ethSTARK documentation – version 1.2. In IACR preprint archive 2021/582, 2023. .
• [Sud97] Madhu Sudan. Decoding of Reed Solomon codes beyond the error-correction bound. In Journal of Complexity, volume 13(1), 1997.
• [WB86] Lloyd R. Welch and Elwyn R. Berlekamp. Error correction for algebraic block codes. US Patent 4633470, 1986. .

In this section we recap well-known facts on decodability of Reed-Solomon codes⁸, and describe the weighted variant of Theorem 1, which is used by the soundness analysis of FRI.

Unless contrary stated, we assume that K is a general field (finite, or infinite), and as for finite fields we shall call

is polynomial in the blocklength n. (Here, B(f,\theta) = \{w \in \mathsf{RS}_k[K,D] : \delta(f,w) < \theta\} is the open -ball around f, and \delta is the fractional Hamming distance.) As in the main part of the document, we throughout assume that both n and k are even.

A.1 Berlekamp-Welch decoder

Assume that f \in K^D is at most \theta_0 -close to V, with \theta_0 = \frac{1-\rho}{2} being the unique decoding radius, and let p(X) be the unique polynomial of degree \leq k-1 such that \delta(f,p) \leq \theta_0 . Then the number of points of disagreement is at most e = \frac{n-k}{2} . The Berlekamp-Welch decoder [WB86] is based on the observation that if \Omega = \{x_1, \ldots, x_e\} is the set of errors, and E(x) = \prod_{x \in \Omega} (X - x) is its vanishing polynomial, then we have

for all x \in D .

1. Find the coefficients of polynomials E(X), G(X) over K with \deg E(X) \leq e , \deg G(X) \leq k-1+e , where e = \frac{n-k}{2} , such that

E(x) \cdot w(x) = G(x) for all x \in D .

This linear system has at least one non-trivial solution which can be found in at most O(n^3) field operations.

Notice that for any such non-trivial solution (E(X), G(X)) the polynomial E(X) must be non-trivial. If E(x) would be identically zero, by the size of D the same is true G(x).

2. For any such non-trivial solution (E(X), G(X)) obtained in step 1, check if G(X) is divisible by E(X). If yes, then output p(X) = \frac{G(X)}{E(X)} . (If not, then abort.)

For a word f \in K^D with fractional Hamming distance of at most \theta_0 , Step (2) of Protocol 4 always succeeds: Let p(X) be the (unique) \theta_0 -close code word. This polynomial agrees with f on a set of size a \ge \frac{n+k}{2} . Consider the bivariate polynomial

^&lt;sup>8The survey by Guruswami [Gur07] is a recommended source.

Then Q(X, p(X)) is a univariate polynomial of degree

which by the assumption on p(X) has at least a zeroes. Consequently Q(X, p(X)) is trivial and p(X) \cdot E(X) = G(X) holds as a formal identity. Since E(X) is non-trivial, we conclude divisibility.

A.2 List decoding

A.2.1 The Sudan decoder

The Sudan list decoder [Sud97] generalizes the Berlekamp-Welch procedure by searching for general bivariate polynomials Q(X,Y) \in K[X,Y] which satisfy

Q(x, f(x)) = 0 for all x \in D .

In order that Y - p(X) is a factor of Q(X, Y) for every polynomial p(X) of degree \leq d = k - 1 which has the claimed agreement set size with f, one looks for such bivariate Q so that the degree of Q(X, p(X)) for any such polynomial is smaller than the targeted agreement set size.

Definition 12. The (1,d)-weighted degree (in short, (1,d)-degree) of a monomial X^i \cdot Y^j is i+d \cdot j . More generally, the (1,d)-weighted degree of a bivariate polynomial Q(X,Y) is the maximum of the weighted degrees of its monomials.

A polynomial Q(X,Y) of (1,d)—weighted degree W is of the form

and its number of coefficients is

1. Solve the linear system on the coefficients of Q(X,Y) with (1,d)-degree W = \lfloor \sqrt{2 \cdot d \cdot n} \rfloor , given by the interpolation constraints

This system has a non-trivial solution which is found in at most O(n^3) field operations. Note that by construction, for any \left(1-\frac{a}{n}\right) -close code word p(X) the (irreducible) polynomial Y-p(X) divides Q(X,Y) in the polynomial ring K[X,Y]. Since K[X,Y] is a unique factorization domain, this already proves that the list size L \leq \left\lfloor \frac{W}{d} \right\rfloor \leq \frac{\sqrt{2 \cdot d \cdot n}}{d} = \sqrt{\frac{2 \cdot n}{d}} .

2. Find all factors of Q(X,Y) which are of the form

Y - p(X) ,

with p(X) being a polynomial over K of degree at most k-1. There are at most \sqrt{\frac{2 \cdot n}{d}} such factors. Filter out those which agree with f on at least a points.

The efficiency of Step (2) depends on the field K. If K is a finite field, then there are polynomial time algorithms (both probabilistic or deterministic) for finding such factors of the form Y - p(X). (They both rely on univariate factorization, see [Gur07], e.g.) If K is infinite, then this might not be true in general.

A.2.2 The Guruswami-Sudan decoder

To extend the interpolation technique to the Johnson limit 1-\sqrt{\rho} , one takes into account that several close codewords might coincide at some points. One therefore looks for polynomials Q(X,Y) the (1,d)-degree of which is m times as large as the targeted agreement set would suggest, and which have a zero of order m at every interpolating point (x, f(x)), x \in D . The parameter m \ge 1 is called multiplicity parameter.

Definition 13. A polynomial Q(X,Y) \in K[X,Y] is said to have a zero of order m at the point (x,y), if the polynomial Q(X-x,Y-y) has no monomial of absolute degree < m.

Such polynomials Q(X,Y) of (1,d)-weighted degree W have still the property, that if p(X) is a polynomial of \deg p(X) \leq d , then

Again, counting the number of coefficients and comparing with the number of interpolation constraints yields that whenever

and hence in particular for W \ge \left\lfloor \sqrt{m \cdot (m+1) \cdot d \cdot n} \right\rfloor there always exists such a (non-trivial) polynomial Q(X,Y). (For details, see [Gur07], e.g.)

1. Solve the linear system on the coefficients of Q(X,Y) with (1,d)-degree W = [\sqrt{m \cdot (m+1) \cdot d \cdot n}] : For each x \in D ,

Q(X,Y) has a zero of order m at (x,f(x)) .

Such a solution always exists and can be found in polynomially many field operations.

By construction, again for any \left(1-\frac{a}{n}\right) -close code word p(X) the irreducible polynomial Y-p(X) divides Q(X,Y). This already proves that the list size L \leq \frac{\sqrt{m \cdot (m+1) \cdot d \cdot n}}{d} < \sqrt{\frac{m \cdot (m+1)}{\rho}} .

1. Find all factors of Q(X,Y) which are of the form

Y - p(X) ,

with p(X) being a polynomial over K of degree at most d = k - 1. There are at most \sqrt{\frac{m \cdot (m+1)}{\rho}} many. Filter out those which agree with f on at least a points.

As before, this step might be efficient or not, depending on the field K.

Remark 14. Choosing the discriminant method to find factors of the form Y - p(X), the Guruswami-Sudan list decoder taking at most

Note that choosing

implies a large enough agreement parameter for the Protocol 6. In particular the choice \alpha = \left(1 + \frac{1}{2m}\right) \cdot \sqrt{\rho} used throughout the main part of the document is strong enough, since

Let us summarize the consequences of Protocol 6.

Theorem 15 (Guruswami-Sudan). Let K be a general (possibly infinite) field, and

L \le \sqrt{\frac{m \cdot (m+1)}{\rho}} \le \frac{m + \frac{1}{2}}{\sqrt{\rho}}. (24)

If K is finite, then the Guruswami-Sudan decoder runs in polynomial time.

We say that a function f \in F^D has \mu -agreement of at least \alpha with another function g \in F^D ,

if there is a set A \subseteq D of measure \mu(A) > \alpha on which both functions agree. Likewise we say that

if there exists a p \in \mathsf{RS}_k[F,D] for which agree_\mu(f,p) > \alpha .

Theorem 16. (Full version of [BCI⁺ 20], Theorem 7.1) Let \theta \in \left(\frac{1-\rho}{2}, 1-\sqrt{\rho}\right) , where \theta = 1-\sqrt{\rho} \cdot \left(1+\frac{1}{2m}\right) , for some integer m \geq 3 , and assume that \mu is a sub-probability measure on D with common denominator M, i.e. for all x in D

for an integer value a_x . Suppose that for f_0, f_1, \ldots, f_{N-1} \in F^D ,

with \varepsilon as in (2). Then there exist polynomials p_0(X) , p_1(X) , ..., p_{N-1}(X) from \mathsf{RS}_k[F,D] , and a set A of density \mu(A) > \alpha on which f_i coincides with p_i for all i = 0, \ldots, N-1 .