Paper 2026/2481

Polygero: Proximity Testing From Polynomial Challenges

Abstract

We present a new proximity test for Reed--Solomon codes that admits a higher-agreement regime with soundness approaching the field's bit length. All prior work in this area [AHIV2017,BCIKS2020,BCHKS2025] uses the idea of *scalar* batching in which the verifier provides a scalar challenge for each codeword, and the prover must supply a codeword equivalent to the combination, and the verifier tests it at randomly opened columns. Our main insight is to instead use a low-degree polynomial challenge for each codeword. We prove that the low-dimensional spaces generated by polynomial challenges become maximum distance separable (MDS) after deleting a few coordinates, and this phenomenon leads to a new kind of proximity gap that we can exploit. This insight enables a simpler, in fact elementary counting proof for soundness of the proximity tests. We do not need the Polishchuk--Spielman lemma or Guruswami--Sudan decoding. The same technique proves soundness of Polygero, a Ligero-inspired IOP~[AHIV17], beyond the unique-decoding regime. Through recursion, Polygero produces proofs with a number of field elements logarithmic in the witness size, independently of the number of linear constraints. It does not require roots of unity in the finite field or out-of-domain sampling. The soundness analysis, including the extractor and the recursive composition, and every reported parameter schedule are machine-checked in Lean.