4

[2011.04295] Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes

 1 year ago
source link: https://arxiv.org/abs/2011.04295
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Computer Science > Information Theory

[Submitted on 9 Nov 2020 (v1), last revised 16 Feb 2021 (this version, v3)]

Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes

Download PDF

In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code C=C(C,P,D) is a vector space associated to evaluations on P of functions in the Riemann-Roch space LC(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 introduced by Ben-Sasson, Bentov, Horesh and Riabzev, known as the FRI protocol. 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. 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. 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.

Subjects: Information Theory (cs.IT); Computational Complexity (cs.CC); Cryptography and Security (cs.CR); Algebraic Geometry (math.AG)
Cite as: arXiv:2011.04295 [cs.IT]
  (or arXiv:2011.04295v3 [cs.IT] for this version)
  https://doi.org/10.48550/arXiv.2011.04295

Submission history

From: Jade Nardi [view email]
[v1] Mon, 9 Nov 2020 10:10:15 UTC (491 KB)
[v2] Tue, 17 Nov 2020 21:38:24 UTC (508 KB)
[v3] Tue, 16 Feb 2021 08:09:21 UTC (71 KB)

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK