Proximity Gaps in Interleaved Codes

Benjamin E. Diamond; Angus Gruen

doi:10.62056/a0ljbkrz

Proximity Gaps in Interleaved Codes

Authors

Benjamin E. Diamond, Angus Gruen

Benjamin E. Diamond

Irreducible, United States
bdiamond at irreducible dot com

Angus Gruen

Polygon, United States
agruen at polygon dot technology

Keywords: proximity testing error-correcting codes proximity gaps

Abstract

A linear error-correcting code exhibits proximity gaps if each affine line of words either consists entirely of words which are close to the code or else contains almost no such words. In this short note, we prove that for each linear code which exhibits proximity gaps within the unique decoding radius, that code's interleaved code also does. Combining our result with a recent argument of Angeris, Evans and Roh ('24), we extend those authors' sharpening of the tensor-based proximity gap of Diamond and Posen (Commun. Cryptol. '24) up to the unique decoding radius, at least in the Reed–Solomon setting.

References

[AER24]

Guillermo Angeris, Alex Evans, and Gyumin Roh. A Note on Ligero and Logarithmic Randomness. Cryptology ePrint Archive, Paper 2024/1399. 2024.

Google Scholar ePrint

[AHIV23]

Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: lightweight sublinear arguments without a trusted setup. Designs, Codes and Cryptography, 2023. DOI: 10.1007/s10623-023-01222-8

Google Scholar ePrint

[BSBHR18]

Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed–Solomon Interactive Oracle Proofs of Proximity. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, International Colloquium on Automata, Languages, and Programming, volume 107 of Leibniz International Proceedings in Informatics, pages 14:1–14:17, Dagstuhl, Germany. 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. DOI: 10.4230/LIPIcs.ICALP.2018.14

Google Scholar ePrint

[BSCI⁺23]

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity Gaps for Reed–Solomon Codes. Journal of the ACM, 70(5), October 2023. DOI: 10.1145/3614423

Google Scholar ePrint

[DP24a]

Benjamin E. Diamond and Jim Posen. Polylogarithmic Proofs for Multilinears over Binary Towers. Cryptology ePrint Archive, Paper 2024/504. 2024.

Google Scholar ePrint

[DP24b]

Benjamin E. Diamond and Jim Posen. Proximity Testing with Logarithmic Randomness. IACR Communications in Cryptology, 1(1), 2024. DOI: 10.62056/aksdkp10

Google Scholar ePrint

[GLS⁺23]

Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, pages 193–226, Cham. 2023. Springer Nature Switzerland. DOI: 10.1007/978-3-031-38545-2_7

Google Scholar ePrint

[Gur06]

Venkatesan Guruswami. Algorithmic Results in List Decoding, volume 2 of Foundations and Trends in Theoretical Computer Science. Number 2 in Foundations and Trends in Theoretical Computer Science. now publishers 2006. DOI: 10.1561/0400000007

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a0ljbkrz

History

Submitted: 2024-09-10
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

Benjamin E. Diamond and Angus Gruen, Proximity Gaps in Interleaved Codes. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a0ljbkrz.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.