论文标题
交互式的甲骨文证明与代数几何代码的邻近性
Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
论文作者
论文摘要
在这项工作中，我们启动了与代数几何（AG）代码的接近度测试的研究。 AG代码$ C = C（\ Mathcal {X}，\ Mathcal {P}，D）$上的代数曲线$ \ Mathcal {X} $是与评估$ \ Mathcal {p} $ riemann-roch Space $ l _ Mathcal中$ \ Mathcal {p} $评估相关的向量空间。测试与错误校正代码$ c $接近的问题在于区分以甲骨文给出的输入单词属于$ c $的情况，而它属于$ c $的每个代码。 AG代码是构建简短系统的良好候选者，但没有对其进行有效的接近测试。我们的目标是填补这一空白。 我们通过将IOPP推广为Ben-Sasson，Bentov，Horesh和Riabzev引入的Reed-Solomon代码（称为FRI协议），为某些AG代码的家族构建了交互式甲骨文证明（IOPP）。我们确定了为AG代码设计有效的IOPP系统的合适要求。我们的方法依赖于在曲线上的小组动作下，在曲线上的小组动作下，任何不变的除数的整洁分解，分解为商曲线上的几个显式Riemann-Roch空间。我们在AG代码$ C $上提供足够的条件，该条件允许将$ C $的接近测试问题减少到较小的代码$ C'$的会员问题。 作为具体的实例，我们在Hermitian塔中研究了Kummer曲线和曲线的AG代码。后者可以通过多层次尺寸的字母定义。我们专注于通用的AG-IOPP结构，可以在Kummer曲线上达到线性供您的运行时间和对数验证，以及在Hermitian Tower上使用Polyrogarithmic验证的Quasilinear Prover时间。
In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\mathcal{X}, \mathcal{P}, D)$ over an algebraic curve $\mathcal{X}$ is a vector space associated to evaluations on $\mathcal{P}$ of functions in the Riemann-Roch space $L_\mathcal{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 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 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.
