ECCC-Report TR20-165https://eccc.weizmann.ac.il/report/2020/165Comments and Revisions published for TR20-165en-usThu, 17 Feb 2022 17:28:23 +0200
Revision 3
| Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes |
Sarah Bordage,
Jade Nardi,
Mathieu Lhotel,
Hugues Randriam
https://eccc.weizmann.ac.il/report/2020/165#revision3In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(X, P, D)$ is a vector space associated to evaluations on $P$ of functions in the Riemann-Roch space $L_X(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 short 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 [Ben-Sasson et al., ICALP 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 thus provide a framework in which a proximity test to $C$ can be reduced to one to a simpler code $C'$. Iterating this process thoroughly, we end up with a membership test to a code with significantly smaller length. 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.Thu, 17 Feb 2022 17:28:23 +0200https://eccc.weizmann.ac.il/report/2020/165#revision3
Revision 2
| Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes |
Sarah Bordage,
Jade Nardi
https://eccc.weizmann.ac.il/report/2020/165#revision2In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\calC, \calP, D)$ is a vector space associated to evaluations on $\calP$ of functions in the Riemann-Roch space $L_\calC(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 \emph{short} 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 (Ben-Sasson, Bentov, Horesh and Riabzev, 2018). We identify suitable requirements for designing efficient IOPP systems for AG codes. Our approach relies on Kani's result that splits 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. Under some hypotheses, a proximity test to $C$ can thus be reduced to one to a simpler code $C'$. Iterating this process thoroughly, we end up with a membership test to a code with significantly smaller length. As a concrete instantiation, we study AG codes on Kummer curves, which are potentially much longer than Reed-Solomon codes. For this type of curves, we manage to extend our generic construction to reach a strictly linear proving time and a strictly logarithmic verification time. Mon, 15 Feb 2021 15:51:57 +0200https://eccc.weizmann.ac.il/report/2020/165#revision2
Revision 1
| Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes |
Sarah Bordage,
Jade Nardi
https://eccc.weizmann.ac.il/report/2020/165#revision1In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\mathcal C, \mathcal P, D)$ is a vector space associated to evaluations on $\mathcal P$ of functions in the Riemann-Roch space $L_\mathcal C(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 \emph{short} 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 \textsf{FRI} protocol and introduced by Ben-Sasson, Bentov, Horesh and Riabzev in 2018. We identify suitable requirements for designing efficient IOPP systems for AG codes. In addition to proposing the first proximity test targeting AG codes, our IOPP admits quasilinear prover arithmetic complexity and sublinear verifier arithmetic complexity with constant soundness for meaningful classes of AG codes. We take advantage of the algebraic geometry framework that makes any group action on the curve that fixes the divisor $D$ translate into a decomposition of the code $C$. Concretely, our approach relies on Kani's result that splits the Riemann-Roch space of any invariant divisor under this action into several explicit Riemann-Roch spaces on the quotient curve. Under some hypotheses, these spaces behave well enough to define an AG code $C'$ on the quotient curve so that a proximity test to $C$ can be reduced to one to $C'$. Iterating this process thoroughly, we end up with a membership test to a code with significantly smaller length.Tue, 17 Nov 2020 23:07:17 +0200https://eccc.weizmann.ac.il/report/2020/165#revision1
Paper TR20-165
| Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes |
Sarah Bordage,
Jade Nardi
https://eccc.weizmann.ac.il/report/2020/165In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\mathcal C, \mathcal P, D)$ is a vector space associated to evaluations on $\mathcal P$ of functions in the Riemann-Roch space $L_\mathcal C(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 \emph{short} 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 \textsf{FRI} protocol and introduced by Ben-Sasson, Bentov, Horesh and Riabzev in 2018. We identify suitable requirements for designing efficient IOPP systems for AG codes. In addition to proposing the first proximity test targeting AG codes, our IOPP admits quasilinear prover arithmetic complexity and sublinear verifier arithmetic complexity with constant soundness for meaningful classes of AG codes. We take advantage of the algebraic geometry framework that makes any group action on the curve that fixes the divisor $D$ translate into a decomposition of the code $C$. Concretely, our approach relies on Kani's result that splits the Riemann-Roch space of any invariant divisor under this action into several explicit Riemann-Roch spaces on the quotient curve. Under some hypotheses, these spaces behave well enough to define an AG code $C'$ on the quotient curve so that a proximity test to $C$ can be reduced to one to $C'$. Iterating this process thoroughly, we end up with a membership test to a code with significantly smaller length.Mon, 09 Nov 2020 14:45:06 +0200https://eccc.weizmann.ac.il/report/2020/165