Stochastic Verification Architectures: ZK-FRS Protocols with Polynomial Blinding, Worst-Case Cryptographic Bounds, and Complete Resolution of the MCA Decoding Limit

This paper presents a formal soundness and privacy analysis for polynomial In-teractive Oracle Proofs (IOPs) utilizing Folding Reed-Solomon (FRS) schemes augmentedwith zero-knowledge polynomial blinding. We combine an explicit worst-case cryptographicreduction with the multivariate interpolation paradigm of Guruswami and Rudra (2008) toestablish protocol stability in high-error regimes. By decoupling query complexity ℓ from theblinding degree slack 𝛽, we eliminate parametric circularity. Specifically, we prove that in-tegrating linear polynomial masking for privacy preserves the underlying algebraic structurerequired to bound candidate list sizes in the Mutual Correlated Agreement (MCA) regionwhere the error radius lies strictly between one minus the square root of the effective coderate 𝜌′ = (𝑘 + 𝛽 − 1)/𝑛 and one minus the effective code rate. By modeling the verifier’s chal-lenge as a formal variable within a trivariate ideal, establishing rigorous coprimality underFRS shift automorphisms in F𝑝[𝑋, 𝑌 ][𝑍], and proving generic non-degeneracy via Jacobiandeterminant bounds over restricted evaluation surfaces, we demonstrate that list growth re-mains strictly bounded by 𝒪((1−𝜌′ −𝜏 )−(𝑠−1)), preventing superpolynomial explosion withoutsacrificing zero-knowledge guarantees. Furthermore, we derive a combined soundness metricincorporating both folding and query bounds to enforce concrete 128-bit security levels underadversarial error distributions.