Paper 2026/2930
BEEP: IOPPs from List Decoding with Better Elimination of Pretenders
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
-
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}
}