betaFeedback

WorksComputer Science

A counterexample to the soundness of the Flowering IOPP for codes on graphs

Abstract

The Flowering protocol of Delavenne, Medevielle and Roussel (ISIT 2025, arXiv:2501.14337) and its generalization by Delavenne and Lallemand (CANS 2025, arXiv:2508.10510) are Interactive Oracle Proofs of Proximity (IOPPs) for codes on graphs with Reed-Solomon local codes. Similarly to FRI for Reed-Solomon codes, the graph is recursively cut into isomorphic subgraphs and the word is folded along the cuts. We show that the soundness claims of both papers are false. The commit soundness proofs identify the vertex distance of a word to the code with the fraction of its unsatisfied local constraints, while only one inequality holds, in the wrong direction. We furthermore give an explicit counterexample.

Introduction

IOPPs like the FRI protocol [1] successively reduce a claim of the form Δ(f,C)≤δ\Delta(f, C) \le\delta for C⊆FnC \subseteq\mathbb{F}^n, f∈Fnf \in\mathbb{F}^n and δ∈[0,1]\delta\in[0, 1] to a claim Δ(f′,C′)≤δ−η\Delta(f', C') \le\delta- \eta with η>0\eta> 0, C′⊆Fn/2C' \subseteq\mathbb{F}^{n/2} and f′∈Fn/2f' \in\mathbb{F}^{n/2} is the folding of ff by some public coin randomness from the Verifier. The soundness analysis of these protocols then rely on the fact that with high probability on the public coin of the Verifier, the folding of a vector ff δ\delta-far from the code CC is (δ−η)(\delta- \eta)-far from C′C'.

In [3] the authors propose an analogous IOPP called Flowering, for codes on graphs [5, 4] whose coordinates are the edges of a regular graph and whose local views must lie in a Reed-Solomon code. The vertices of the graph are cut into two subsets of vertices, and the subvectors on the induced subgraphs are combined linearly. This construction is extended in [2] to collections of non-disjoint cuts. Both papers claim a soundness error smaller than that of FRI, valid up to the covering radius. However these soundness claims are false.

In Section 3, we locate the flaw in the proofs of commit soundness [3 Proposition 3] and [2 Proposition 4], we show that folding along a flowering cut does not preserve the Hamming distance, and we give a word on which a cheating Prover contradicts the soundness theorems of both papers.

Definitions and claim

We follow the definitions and notations of [3].

Definition 1 (nn-RIM). For n∈Nn \in\mathbb{N}, an nn-regular indexed multigraph (nn-RIM) Γ=(V,E)\Gamma= (V, E) is given by a map E:V×[n]→VE: V \times[n] \to V such that for all v∈Vv \in V and ℓ∈[n]\ell\in[n], E(E(v,ℓ),ℓ)=vE(E(v, \ell), \ell) = v.

We say that (v,ℓ)(v, \ell) is a petal if E(v,ℓ)=vE(v, \ell) = v. A word on Γ\Gamma is a map f:V×[n]→Ff: V \times[n] \to\mathbb{F} such that for all v∈Vv \in V and ℓ∈[n]\ell\in[n], f(v,ℓ)=f(E(v,ℓ),ℓ)f(v, \ell) = f(E(v, \ell), \ell). Denote W(Γ,F)W(\Gamma, \mathbb{F}) the set of words on Γ\Gamma.

For f∈W(Γ,F)f \in W(\Gamma,\mathbb{F}) and v∈Vv \in V, denote f(v,⋅)=(f(v,1),…,f(v,n))∈Fnf(v,\cdot)=(f(v,1),\ldots,f(v,n))\in\mathbb{F}^{n} the local view of ff at vv.

Definition 2 (Code C[Γ,k]C[\Gamma,k]). Let k≤nk \le n and let RS⁡[n,k]\operatorname{RS}[n,k] be a Reed-Solomon code of length nn and dimension kk. The code on Γ\Gamma is defined by

C[Γ,k]:={f∈W(Γ,F)∣∀v∈V, f(v,⋅)∈RS⁡[n,k]}.C[\Gamma,k]:=\{f\in W(\Gamma,\mathbb{F})\mid\forall v\in V,\ f(v,\cdot)\in\operatorname{RS}[n,k]\}.

Denote ΔH\Delta_H the relative Hamming distance, i.e. for f,g∈W(Γ,F)f,g\in W(\Gamma,\mathbb{F}), ΔH(f,g)\Delta_H(f,g) is the fraction of edges on which ff and gg differ. For f∈W(Γ,F)f\in W(\Gamma,\mathbb{F}) and S⊆W(Γ,F)S\subseteq W(\Gamma,\mathbb{F}), ΔH(f,S):=min⁡g∈SΔH(f,g)\Delta_H(f,S):=\min_{g\in S}\Delta_H(f,g).

Definition 3 (Cut-graph). For V′⊆VV'\subseteq V, the cut-graph Cut⁡[Γ,V′]=(V′,E′)\operatorname{Cut}[\Gamma,V']=(V',E') is defined by E′(v,ℓ)=E(v,ℓ)E'(v,\ell)=E(v,\ell) if E(v,ℓ)∈V′E(v,\ell)\in V' and E′(v,ℓ)=vE'(v,\ell)=v otherwise. The edges leaving V′V' become petals.

Definition 4 (Flowering cut). A flowering cut is a partition V=V′⊔V′′V=V'\sqcup V'' together with a bijection φ:V′→V′′\varphi:V'\to V'' that is an index-preserving isomorphism from Cut⁡[Γ,V′]\operatorname{Cut}[\Gamma,V'] to Cut⁡[Γ,V′′]\operatorname{Cut}[\Gamma,V''].

Denote πφ:V→V′\pi_\varphi:V\to V' for the map equal to the identity on V′V' and to φ−1\varphi^{-1} on V′′V''.

Definition 5 (Folding). For α∈F\alpha\in\mathbb{F}, the folding of f∈W(Γ,F)f\in W(\Gamma,\mathbb{F}) is the word Fold⁡[f,α]∈W(Cut⁡[Γ,V′],F)\operatorname{Fold}[f,\alpha]\in W(\operatorname{Cut}[\Gamma,V'],\mathbb{F}) given for v∈V′v\in V' and ℓ∈[n]\ell\in[n] by

Fold⁡[f,α](v,ℓ)=f(v,ℓ)+αf(φ(v),ℓ).\operatorname{Fold}[f,\alpha](v,\ell)=f(v,\ell)+\alpha f(\varphi(v),\ell).

Definition 6 (Blossoming sequence). A blossoming sequence is a sequence of nn-RIMs Γ0,…,Γr\Gamma_0,\ldots,\Gamma_r such that Γr\Gamma_r has a single vertex and each Γi\Gamma_i is the cut-graph Cut⁡[Γi−1,Vi]\operatorname{Cut}[\Gamma_{i-1},V_i] of a flowering cut (Vi,φi)(V_i,\varphi_i) of Γi−1\Gamma_{i-1}.

For a blossoming sequence, denote Ci:=C[Γi,k]C_i:=C[\Gamma_i,k] and πi:=πφi\pi_i:=\pi_{\varphi_i}; when applied to a word on Γi−1\Gamma_{i-1}, Fold⁡\operatorname{Fold} denotes the folding along (Vi,φi)(V_i,\varphi_i).

We present the Flowering protocol of [3 Protocol 1] with parameter t=nt=n.

Definition 7 (Flowering protocol [3 Protocol 1]). Let m≥1m\ge1 and f0∈W(Γ0,F)f_0\in W(\Gamma_0,\mathbb{F}). The Flowering protocol is the following interactive protocol between a Prover and a Verifier where the Prover has access to f0f_0 and the Verifier has oracle access to f0f_0.

  • Commit phase. For i=1,…,ri=1,\ldots,r, the Verifier sends a uniformly random αi−1∈F\alpha_{i-1}\in\mathbb{F}, and the Prover answers with oracle access to some fi∈W(Γi,F)f_i\in W(\Gamma_i,\mathbb{F}).

  • Query phase, repeated independently mm times. The Verifier picks a uniformly random v0∈V0v_0\in V_0, and sets vi=πi(vi−1)v_i=\pi_i(v_{i-1}) for i∈[r]i\in[r]. It checks that Fold⁡[fi−1,αi−1](vi,⋅)=fi(vi,⋅)\operatorname{Fold}[f_{i-1},\alpha_{i-1}](v_i,\cdot)=f_i(v_i,\cdot) for all i∈[r]i\in[r], and that fr(vr,⋅)∈RS⁡[n,k]f_r(v_r,\cdot)\in\operatorname{RS}[n,k].

The main result of [3, 2] is the soundness of the Flowering protocol [2 Theorem 2], which generalizes [3 Theorem 2] to collections of non-disjoint cuts. A flowering cut as above is a flowering cut collection of order 2 in the sense of [2 Definition 7]. For such collections, the protocol of [2 Definition 10] is the one above, where the Verifier reads whole local views (μ=1\mu=1 in [2]). With rr rounds and mm repetitions, [2 Theorem 2] then reads as follows.

Flawed claim 8 ([2 Theorem 2]). Let k<nk<n, let (Γ0,…,Γr)(\Gamma_0,\ldots,\Gamma_r) be a blossoming sequence and let f0∈W(Γ0,F)f_0\in W(\Gamma_0,\mathbb{F}). For every Prover, the Verifier of the Flowering protocol accepts f0f_0 with probability at most

min⁡ε>0(rε∣F∣+(1−ΔH(f0,C0)+rε)m).\min_{\varepsilon>0}\left(\frac{r}{\varepsilon|\mathbb{F}|}+\left(1-\Delta_H(f_0,C_0)+r\varepsilon\right)^m\right).

We give a counterexample to Flawed claim 8 in § 3.2.

Counterexamples

For f∈W(Γ,F)f \in W(\Gamma,\mathbb{F}), let U(f):={v∈V:f(v,⋅)∉RS⁡[n,k]}U(f) := \{v \in V : f(v,\cdot) \notin\operatorname{RS}[n,k]\} be its set of unsatisfied vertices. Both papers prove Flawed claim 8 through a commit-soundness statement [3 Proposition 3], [2 Proposition 4] in the vertex distance ΔV(f,g):=∣{v∈V:f(v,⋅)≠g(v,⋅)}∣/∣V∣\Delta_V(f,g) := |\{v \in V : f(v,\cdot) \ne g(v,\cdot)\}|/|V|. Its proof sets δ:=ΔV(f,C)\delta:= \Delta_V(f,C) and T:=U(f)T := U(f), and uses ∣T∣=δ∣V∣|T| = \delta|V| (just before [3 Equation (3)], just after [2 Equation (6)]). Only ∣T∣≤δ∣V∣|T| \le\delta|V| holds: a codeword differs from ff at every unsatisfied vertex, and possibly at many others (§ 3.2).

Folding does not preserve the Hamming distance

We first show that folding may drastically decrease the Hamming distance, which rules out a proof similar to that of FRI.

Proposition 9. Let n≥3n \ge3, ∣F∣>n|\mathbb{F}| > n, k=1k = 1, and let Γ0\Gamma_0 have two vertices v1,v2v_1,v_2 sharing the edge of index 1, each with n−1n-1 petals (Figure 1). With V′={v1}V' = \{v_1\} and φ(v1)=v2\varphi(v_1) = v_2, the word ff given by f(v1,⋅)=0f(v_1,\cdot) = 0 and f(v2,⋅)=(0,1,…,1)f(v_2,\cdot) = (0,1,\ldots,1) satisfies, for every α∈F\alpha\in\mathbb{F},

ΔH(f,C0)=n−12n−1andΔH(Fold⁡[f,α],C1)≤1n.\Delta_H(f,C_0) = \frac{n-1}{2n-1} \qquad\text{and}\qquad \Delta_H(\operatorname{Fold}[f,\alpha],C_1) \le\frac{1}{n}.

Proof. Since RS⁡[n,1]\operatorname{RS}[n,1] is the set of constant vectors and v1,v2v_1,v_2 share an edge, C0C_0 is the set of constant words. The word ff equals 1 on the n−1n-1 petals of v2v_2 and 0 on the nn other edges. Hence ff is at distance n−1n-1 from the zero word, nn from the all-one word, and 2n−12n-1 from the other constant words, and ΔH(f,C0)=(n−1)/(2n−1)\Delta_H(f,C_0) = (n-1)/(2n-1).

Moreover,

Fold⁡[f,α](v1,⋅)=f(v1,⋅)+αf(v2,⋅)=α(0,1,…,1),\operatorname{Fold}[f,\alpha](v_1,\cdot) = f(v_1,\cdot) + \alpha f(v_2,\cdot) = \alpha(0,1,\ldots,1),

which differs from α(1,…,1)∈C1\alpha(1,\ldots,1) \in C_1 on a single edge out of nn.

Figure 1. Proposition 9 for n=5n=5. The common edge becomes the red petal, the only edge where Fold⁡[f,α]\operatorname{Fold}[f,\alpha] differs from the codeword α(1,…,1)\alpha(1,\ldots,1).

This does not contradict Flawed claim 8: for α≠0\alpha\ne0, the folding is not a codeword and the Verifier reads the whole local view of the single vertex of Γ1\Gamma_1. We now hide the error at one vertex among many.

The claim is false

Fix r≥3r \ge3, N=2rN = 2^r, n=N−1n = N-1, k=N/2k = N/2, so that RS⁡[n,k]\operatorname{RS}[n,k] has minimum distance N/2N/2. Fix a field F\mathbb{F} of odd characteristic with ∣F∣>n|\mathbb{F}| > n. Let Γ0=Cay⁡(F2r,S)\Gamma_0 = \operatorname{Cay}(\mathbb{F}_2^r,S) with S=F2r∖{0}={s1,…,sn}S = \mathbb{F}_2^r \setminus\{0\} = \{s_1,\ldots,s_n\}, that is E(v,ℓ)=v+sℓE(v,\ell) = v+s_\ell. Then Γ0\Gamma_0 is the complete graph KNK_N. Let Γ0,…,Γr\Gamma_0,\ldots,\Gamma_r be the blossoming sequence of [3 Definition 10]: Vi={0}i×F2r−iV_i = \{0\}^i \times\mathbb{F}_2^{r-i} and φi(v)=v+ei\varphi_i(v) = v + e_i, with eie_i the ii-th unit vector. Write V′=V1V' = V_1, V′′=V0∖V1V'' = V_0 \setminus V_1, φ=φ1\varphi= \varphi_1. Every vertex of Γ1\Gamma_1 has a petal at each index of L×:={ℓ:the first coordinate of sℓ is 1}L_\times:= \{\ell: \text{the first coordinate of }s_\ell\text{ is }1\}. This is illustrated in Figure 2.

First cut for r = 3 and s_{\ell_0} = e_1

Figure 2. First cut for r=3r = 3 and sℓ0=e1s_{\ell_0} = e_1. The gray edges cross the cut and become petals of Γ1\Gamma_1. The only unsatisfied vertex of ff is v∗v^*, and Fold⁡[f,α]\operatorname{Fold}[f,\alpha] becomes a codeword after changing the red petal.

We first show in Lemma 10 that for every vertex v∗v^*, there are words on Γ0\Gamma_0 whose only unsatisfied vertex is v∗v^*.

Lemma 10. For every v∗∈V0v^* \in V_0 and e∈Fne \in\mathbb{F}^n, there is f∈W(Γ0,F)f \in W(\Gamma_0,\mathbb{F}) with f(v,⋅)∈RS⁡[n,k]f(v,\cdot) \in\operatorname{RS}[n,k] for v≠v∗v \ne v^* and f(v∗,⋅)−e∈RS⁡[n,k]f(v^*,\cdot)-e \in\operatorname{RS}[n,k].

Proof. Denote RS⁡⊥\operatorname{RS}^{\perp} the dual code of RS⁡[n,k]\operatorname{RS}[n,k]. It is an MDS code of dimension n−kn-k, hence of minimum distance k+1k+1.

We first show that the N(n−k)N(n-k) local parity checks are linearly independent. Let (hv)v∈V0∈(RS⁡⊥)V0(h_v)_{v\in V_0} \in(\operatorname{RS}^{\perp})^{V_0} such that for all f∈W(Γ0,F)f \in W(\Gamma_0,\mathbb{F}),

∑v∈V0∑ℓ∈[n]hv(ℓ)f(v,ℓ)=0.\sum_{v\in V_0}\sum_{\ell\in[n]} h_v(\ell)f(v,\ell)=0.

Since the value of ff on the edge {v,v+sℓ}\{v,v+s_\ell\} appears in both f(v,ℓ)f(v,\ell) and f(v+sℓ,ℓ)f(v+s_\ell,\ell), this is equivalent to

∀v∈V0, ∀ℓ∈[n],hv(ℓ)+hv+sℓ(ℓ)=0.(1)\forall v \in V_0,\ \forall\ell\in[n],\qquad h_v(\ell)+h_{v+s_\ell}(\ell)=0. \tag*{(1)}

For b∈F2rb \in\mathbb{F}_2^r, denote χb(v):=(−1)b⋅v∈F\chi_b(v):=(-1)^{b\cdot v}\in\mathbb{F} and h^b:=∑v∈V0χb(v)hv∈RS⁡⊥\widehat{h}_b:=\sum_{v\in V_0}\chi_b(v)h_v\in\operatorname{RS}^{\perp}. Multiplying (1) by χb(v)\chi_b(v), summing over v∈V0v\in V_0 and using χb(v)=χb(v+sℓ)χb(sℓ)\chi_b(v)=\chi_b(v+s_\ell)\chi_b(s_\ell), we obtain

∀ℓ∈[n],(1+χb(sℓ))h^b(ℓ)=0.\forall\ell\in[n],\qquad(1+\chi_b(s_\ell))\widehat{h}_b(\ell)=0.

Since the characteristic of F\mathbb{F} is odd, $1+\chi_b(s_\ell)=2\ne0$ whenever b⋅sℓ=0b\cdot s_\ell=0, and then h^b(ℓ)=0\widehat{h}_b(\ell)=0. If b=0b=0, this holds for all ℓ∈[n]\ell\in[n], so h^0=0\widehat{h}_0=0. If b≠0b\ne0, this holds for the N/2−1N/2-1 indices ℓ\ell such that sℓ∈b⊥s_\ell\in b^\perp, so h^b\widehat{h}_b has weight at most n−(N/2−1)=k<k+1n-(N/2-1)=k<k+1, and h^b=0\widehat{h}_b=0. Since NN is invertible in F\mathbb{F}, the Fourier inversion formula gives for all $v\in V_0

hv=1N∑b∈F2rχb(v)h^b=0.h_v=\frac{1}{N}\sum_{b\in\mathbb{F}_2^r}\chi_b(v)\widehat{h}_b=0.

Therefore the local parity checks are linearly independent.

Now let C−v∗⊆W(Γ0,F)C_{-v^*}\subseteq W(\Gamma_0,\mathbb{F}) be the space of words whose local views at all v≠v∗v\ne v^* lie in RS⁡[n,k]\operatorname{RS}[n,k], and consider

σ:C−v∗→Fn/RS⁡[n,k],f↦f(v∗,⋅)+RS⁡[n,k].\sigma:C_{-v^*}\to\mathbb{F}^n/\operatorname{RS}[n,k],\qquad f\mapsto f(v^*,\cdot)+\operatorname{RS}[n,k].

Its kernel is C0C_0, and by independence of the local parity checks, dim⁡C−v∗−dim⁡C0=n−k\dim C_{-v^*}-\dim C_0=n-k. Hence σ\sigma is surjective, which proves the lemma. □

We then show in Lemma 11 that such words are far from the code.

Lemma 11. If U(f)={v∗}U(f)=\{v^*\}, then ΔH(f,C0)≥ηN:=N2+44N(N−1)>max⁡(14,2N)\Delta_H(f,C_0)\geq\eta_N:=\frac{N^2+4}{4N(N-1)}>\max\left(\frac{1}{4},\frac{2}{N}\right).

Proof. For x∈Fnx\in\mathbb{F}^n, denote ∣x∣|x| its Hamming weight. Let c∈C0c\in C_0, and denote y:=f−cy:=f-c and

D:={v∈V0∖{v∗}∣y(v,⋅)≠0}.D:=\{v\in V_0\setminus\{v^*\}\mid y(v,\cdot)\ne0\}.

Since f(v∗,⋅)∉RS[n,k]f(v^*,\cdot)\notin\mathrm{RS}[n,k] and c(v∗,⋅)∈RS[n,k]c(v^*,\cdot)\in\mathrm{RS}[n,k], we have y(v∗,⋅)≠0y(v^*,\cdot)\ne0. Remark that if y(v,ℓ)≠0y(v,\ell)\ne0, then y(v+sℓ,ℓ)=y(v,ℓ)≠0y(v+s_\ell,\ell)=y(v,\ell)\ne0, so v+sℓ∈D∪{v∗}v+s_\ell\in D\cup\{v^*\}. In particular D≠∅D\ne\varnothing.

Let w∈Dw\in D. Since w≠v∗w\ne v^*, y(w,⋅)y(w,\cdot) is a nonzero codeword of RS[n,k]\mathrm{RS}[n,k], so ∣y(w,⋅)∣≥n−k+1=N/2|y(w,\cdot)|\geq n-k+1=N/2. As Γ0\Gamma_0 has no multiple edges, these N/2N/2 nonzero coordinates lead to N/2N/2 distinct vertices of (D∪{v∗})∖{w}(D\cup\{v^*\})\setminus\{w\}, hence ∣D∣≥N/2|D|\geq N/2.

Each edge on which yy is nonzero is counted twice in ∑v∈V0∣y(v,⋅)∣\sum_{v\in V_0}|y(v,\cdot)|. Therefore yy is nonzero on at least half of

∑v∈V0∣y(v,⋅)∣≥∣y(v∗,⋅)∣+∑w∈D∣y(w,⋅)∣≥1+N2∣D∣≥1+N24.\sum_{v\in V_0}|y(v,\cdot)|\geq|y(v^*,\cdot)|+\sum_{w\in D}|y(w,\cdot)|\geq1+\frac{N}{2}|D|\geq1+\frac{N^2}{4}.

edges, out of the N(N−1)/2N(N-1)/2 edges of Γ0\Gamma_0. Thus ΔH(f,c)≥ηN\Delta_H(f,c)\geq\eta_N. Finally, ηN>1/4\eta_N>1/4 since N2+4>N2−NN^2+4>N^2-N, and ηN>2/N\eta_N>2/N since N2+4−8(N−1)=(N−2)(N−6)>0N^2+4-8(N-1)=(N-2)(N-6)>0 for N≥8N\geq8. □

We finally show in Proposition 12 that a cheating Prover makes the Verifier accept such a word with high probability.

Proposition 12. Let v∗∈V′′v^*\in V^{\prime\prime}, u∗=v∗+e1u^*=v^*+e_1, ℓ0∈L×\ell_0\in L_\times, and ff given by Lemma 10 with e=1ℓ0e=1_{\ell_0}. For every m≥1m\geq1, a Prover makes the Verifier accept ff with probability at least (1−2/N)m(1-2/N)^m, whereas the bound of Flawed claim 8 tends to at most (1−ηN)m<(1−2/N)m(1-\eta_N)^m<(1-2/N)^m as ∣F∣→∞|\mathbb{F}|\to\infty. Hence Flawed claim 8 and [3 Theorem 2] are false.

Proof. Since 1ℓ01_{\ell_0} has weight 1<N/21<N/2, we have 1ℓ0∉RS[n,k]1_{\ell_0}\notin\mathrm{RS}[n,k], hence U(f)={v∗}U(f)=\{v^*\}.

We first describe the Prover. Let α0∈F\alpha_0\in\mathbb{F} be the first challenge of the Verifier, and let gg be the word equal to Fold⁡[f,α0]\operatorname{Fold}[f,\alpha_0] except at (u∗,ℓ0)(u^*,\ell_0), where

g(u∗,ℓ0):=Fold⁡[f,α0](u∗,ℓ0)−α0.g(u^*,\ell_0):=\operatorname{Fold}[f,\alpha_0](u^*,\ell_0)-\alpha_0.

Since ℓ0∈L×\ell_0\in L_\times, (u∗,ℓ0)(u^*,\ell_0) is a petal of Γ1\Gamma_1, so g∈W(Γ1,F)g\in W(\Gamma_1,\mathbb{F}). Let u∈V′u\in V'. If u≠u∗u\ne u^*, then neither uu nor φ(u)\varphi(u) is v∗v^*, hence

g(u,⋅)=f(u,⋅)+α0f(φ(u),⋅)∈RS[n,k].g(u,\cdot)=f(u,\cdot)+\alpha_0f(\varphi(u),\cdot)\in\mathrm{RS}[n,k].

If u=u∗u=u^*, then by Lemma 10,

g(u∗,⋅)=f(u∗,⋅)+α0(f(v∗,⋅)−1ℓ0)∈RS[n,k].g(u^*,\cdot)=f(u^*,\cdot)+\alpha_0(f(v^*,\cdot)-1_{\ell_0})\in\mathrm{RS}[n,k].

Thus g∈C1g\in C_1. The Prover sends f1:=gf_1:=g, and then fi:=Fold⁡[fi−1,αi−1]f_i:=\operatorname{Fold}[f_{i-1},\alpha_{i-1}] for i=2,…,ri=2,\ldots,r. Since each local view of a folding is a linear combination of local views, fi∈Cif_i\in C_i for all i∈[r]i\in[r]. We now bound the acceptance probability. The checks of rounds i≥2i \ge2 pass by construction, and the final check passes since fr∈Crf_r \in C_r. Since Fold⁡[f0,α0]\operatorname{Fold}[f_0,\alpha_0] and f1f_1 differ at most at (u∗,ℓ0)(u^*,\ell_0), the check of round 1 fails only if v1=u∗v_1=u^*. As π1\pi_1 is two-to-one from V0V_0 onto V′V', this happens with probability 2/N2/N. The mm repetitions being independent, the Verifier accepts with probability at least (1−2/N)m(1-2/N)^m.

Finally, taking ε:=∣F∣−1/2\varepsilon:=|\mathbb{F}|^{-1/2} in Flawed claim 8 and using Lemma 11, the bound of Flawed claim 8 is at most

r∣F∣+(1−ηN+r∣F∣)m→∣F∣→∞(1−ηN)m.\frac{r}{\sqrt{|\mathbb{F}|}}+\left(1-\eta_N+\frac{r}{\sqrt{|\mathbb{F}|}}\right)^m \xrightarrow{|\mathbb{F}|\to\infty} (1-\eta_N)^m.

which is smaller than (1−2/N)m(1-2/N)^m since ηN>2/N\eta_N>2/N. The bound of [3 Theorem 2] multiplies ΔH(f0,C0)\Delta_H(f_0,C_0) by a constant that equals 1 when Γ0\Gamma_0 has no petals [3 Proposition 1], so it is the same here. □\square

For instance, let r=3r=3 and m=1m=1. Since Hamming weights are integers, Lemma 11 shows that ff is at distance at least 9 of the 28 edges of K8K_8 from C0C_0. The Prover is accepted with probability at least 3/43/4, while Flawed claim 8 with ε=1/84\varepsilon=1/84 gives at most 5/7+252/∣F∣<3/45/7+252/|\mathbb{F}|<3/4 for ∣F∣>7056|\mathbb{F}|>7056. For larger rr, the Prover is accepted with probability at least 1−2m/2r1-2m/2^r, while the bound of Flawed claim 8 tends to at most (3/4)m(3/4)^m.

References

  1. [1][BBHR18] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev. Fast Reed–Solomon interactive oracle proofs of proximity. In ICALP 2018, volume 107 of LIPIcs, pages 14:1–14:17, 2018.
  2. [2][DL25] H. Delavenne and L. Lallemand. Codes on any Cayley graph have an interactive oracle proof of proximity. In CANS 2025, volume 16351 of LNCS, pages 335–357. Springer, 2026. arXiv:2508.10510.arxiv.org/abs/2508.10510
  3. [3][DMR25] H. Delavenne, T. Medevielle, and É. Roussel. Interactive oracle proofs of proximity to codes on graphs. In IEEE International Symposium on Information Theory (ISIT), 2025. arXiv:2501.14337.arxiv.org/abs/2501.14337
  4. [4][SS96] M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710–1722, 1996.
  5. [5][Tan81] R. M. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533–547, 1981.DOI

Paper details

vlnc:W_sfag3eq6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents