DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.24

All Polynomial Generators Preserve Distance with Mutual Correlated Agreement

Authors: Sarah Bordage, Alessandro Chiesa, Ziyi Guan, and Ignacio Manzur

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

A generator is a function that maps a random seed to a list of coefficients. We study generators that preserve distance to a linear code: the linear combination of any list of vectors using coefficients sampled by the generator has distance to the code no smaller than that of the original vectors, except for a small error. Distance preservation plays a central role in modern probabilistic proofs, and has been formalized in several ways. We study mutual correlated agreement, the strongest known form of distance preservation. We initiate a systematic study of mutual correlated agreement, aiming to characterize the class of generators with this property. Towards this, we study polynomial generators, a rich class that includes all examples of generators considered in the distance preservation literature. Our main result is that all polynomial generators guarantee mutual correlated agreement for every linear code. This improves on prior work both in generality (the class of generators covered) and in parameters (the error bounds). We additionally provide new results for the case where the linear code is a Reed-Solomon code, which is of particular interest in applications. We prove that all polynomial generators satisfy mutual correlated agreement for Reed-Solomon codes up to the Johnson bound. In particular, we improve upon the state-of-the-art by Ben-Sasson, Carmon, Ishai, Kopparty, and Saraf (FOCS 2020) and answer a question posed by Arnon, Chiesa, Fenzi, and Yogev (Eurocrypt 2025). Along the way we develop a flexible and general toolbox for mutual correlated agreement, and are the first to establish distance preservation for generators that lie beyond polynomial generators.

Cite as

Sarah Bordage, Alessandro Chiesa, Ziyi Guan, and Ignacio Manzur. All Polynomial Generators Preserve Distance with Mutual Correlated Agreement. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bordage_et_al:LIPIcs.CCC.2026.24,
  author =	{Bordage, Sarah and Chiesa, Alessandro and Guan, Ziyi and Manzur, Ignacio},
  title =	{{All Polynomial Generators Preserve Distance with Mutual Correlated Agreement}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.24},
  URN =		{urn:nbn:de:0030-drops-270666},
  doi =		{10.4230/LIPIcs.CCC.2026.24},
  annote =	{Keywords: proximity testing, distance preservation, mutual correlated agreement}
}

Document

DOI: 10.4230/LIPIcs.CCC.2022.30

Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes

Authors: Sarah Bordage, Mathieu Lhotel, Jade Nardi, and Hugues Randriam

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract

In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code C = C(𝒳, 𝒫, D) over an algebraic curve 𝒳 is a vector space associated to evaluations on 𝒫 ⊆ 𝒳 of functions in the Riemann-Roch space L_𝒳(D). The problem of testing proximity to an error-correcting code C consists in distinguishing between the case where an input word, given as an oracle, belongs to C and the one where it is far from every codeword of C. AG codes are good candidates to construct probabilistic proof systems, but there exists no efficient proximity tests for them. We aim to fill this gap. We construct an Interactive Oracle Proof of Proximity (IOPP) for some families of AG codes by generalizing an IOPP for Reed-Solomon codes, known as the FRI protocol [Eli Ben-Sasson et al., 2018]. We identify suitable requirements for designing efficient IOPP systems for AG codes. Our approach relies on a neat decomposition of the Riemann-Roch space of any invariant divisor under a group action on a curve into several explicit Riemann-Roch spaces on the quotient curve. We provide sufficient conditions on an AG code C that allow to reduce a proximity testing problem for C to a membership problem for a significantly smaller code C'. As concrete instantiations, we study AG codes on Kummer curves and curves in the Hermitian tower. The latter can be defined over polylogarithmic-size alphabet. We specialize the generic AG-IOPP construction to reach linear prover running time and logarithmic verification on Kummer curves, and quasilinear prover time with polylogarithmic verification on the Hermitian tower.

Cite as

Sarah Bordage, Mathieu Lhotel, Jade Nardi, and Hugues Randriam. Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 30:1-30:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bordage_et_al:LIPIcs.CCC.2022.30,
  author =	{Bordage, Sarah and Lhotel, Mathieu and Nardi, Jade and Randriam, Hugues},
  title =	{{Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{30:1--30:45},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.30},
  URN =		{urn:nbn:de:0030-drops-165923},
  doi =		{10.4230/LIPIcs.CCC.2022.30},
  annote =	{Keywords: Algebraic geometry codes, Interactive oracle proofs of proximity, Proximity testing}
}

Search Results

Documents authored by Bordage, Sarah

All Polynomial Generators Preserve Distance with Mutual Correlated Agreement

Abstract

Cite as

Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes

Abstract

Cite as

Thanks for your feedback!

Could not send message