License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2022.30
URN: urn:nbn:de:0030-drops-165923
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16592/
Bordage, Sarah ;
Lhotel, Mathieu ;
Nardi, Jade ;
Randriam, Hugues
Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
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.
BibTeX - Entry
@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/opus/volltexte/2022/16592},
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}
}
|
Keywords: |
|
Algebraic geometry codes, Interactive oracle proofs of proximity, Proximity testing |
|
Collection: |
|
37th Computational Complexity Conference (CCC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
11.07.2022 |
