Paper 2026/2930

BEEP: IOPPs from List Decoding with Better Elimination of Pretenders

Remco Bloemen, World Foundation
Albert Garreta, World Foundation
Abstract

We present an improved soundness analysis of the DEEP technique for linear codes (after a minor modification), which, unlike its predecessor, results in negligible error bounds for parameters typically used in practice. The modification consists simply in performing $m$ DEEP samples, instead of one. The resulting DEEP sampling error decreases exponentially with $m$, and in practice $m=2$-$5$ makes it tiny. The subsequent folding error is of $(\delta \cdot n +1)/|\mathbb{F}|$, for $\delta$ a proximity parameter and $n$ the code length. We modify typical code-based IOPPs with this technique, such as WHIR, Ligerito, Basefold, etc. As a result, we obtain code-based IOPPs that only require list decodability of the underlying codes, instead of Mutual Correlated Agreement (MCA), with smaller soundness errors than their counterparts. Since it does not rely on MCA for its soundness, this improved DEEP technique allows to use arbitrary linear codes in IOPPs with $delta$ up to the Johnson bound. Additionally, this opens the door to using codes (e.g. perhaps Reed-Solomon codes) with $\delta$ beyond the Johnson bound, assuming the code is $\delta$-list decodable, even if it does not have the $\delta$-MCA property. Finally, we also provide an affine version of our improved DEEP analysis, where the folding challenges are affine polynomials instead of field elements, following [FS26,CWYZ26]. We provide a simple proof showing that, after the DEEP samples are done, the folding error with affine folding challenges is $2/|\mathbb{F}|$, which is smaller than the affine-MCA error from @CWYZ26.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
List decodabilitylinear codescorrelated agreementFRISNARKsIOPIOPPproximity gaps
Contact author(s)
remco @ world org
albert @ world org
History
2026-11-22: approved
2026-11-18: received
See all versions
Short URL
https://ia.cr/2026/2930
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2930,
      author = {Remco Bloemen and Albert Garreta},
      title = {{BEEP}: {IOPPs} from List Decoding with Better Elimination of Pretenders},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2930},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2930}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.