Document Open Access Logo

Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes

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

PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.30.pdf
  • Filesize: 1.11 MB
  • 45 pages

Document Identifiers

Author Details

Sarah Bordage
  • LIX, CNRS UMR 7161, Ecole Polytechnique, Institut Polytechnique de Paris, France
  • Inria, Palaiseau, France
Mathieu Lhotel
  • Laboratoire de Mathématiques de Besançon, UMR 6623 CNRS, Université de Bourgogne Franche-Comté, France
Jade Nardi
  • Univ Rennes, CNRS, IRMAR - UMR 6625, F-35000 Rennes, France
Hugues Randriam
  • ANSSI, Paris, France
  • Institut Polytechnique de Paris, Télécom Paris, Palaiseau, France

Funding

This work was funded in part by the grant ANR-21-CE39-0009 - BARRACUDA from the French National Research Agency.
  • Bordage, Sarah: Supported by the Chair "Blockchain & B2B Platforms", led by l'X - {É}cole Polytechnique and the Fondation de l'{É}cole Polytechnique, sponsored by Capgemini, NomadicLabs and Caisse des Dépôts.
  • Nardi, Jade: Suported by the French government "Investissements d’Avenir" program ANR-11-LABX-0020-01.

Acknowledgements

The authors are very appreciative to the anonymous reviewers whose comments and suggestions helped to improve and clarify this manuscript. The third author thanks Marc Perret for his precious advice in the early days of this project. The authors are grateful to Daniel Augot for suggesting to work on this project and for many valuable discussions. They also thank Eli Ben-Sasson and Alessandro Chiesa for their helpful insights.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.CCC.2022.30

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
  • Theory of computation → Interactive proof systems
Keywords
  • Algebraic geometry codes
  • Interactive oracle proofs of proximity
  • Proximity testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight Sublinear Arguments Without a Trusted Setup. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 2087-2104. ACM, 2017. URL: https://doi.org/10.1145/3133956.3134104.
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45(3):501-555, 1998. extended version of FOCS'92. URL: https://doi.org/10.1145/278298.278306.
  3. Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs; A New Characterization of NP. In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 2-13. IEEE Computer Society, 1992. URL: https://doi.org/10.1145/273865.273901.
  4. Daniel Augot, Sarah Bordage, and Jade Nardi. Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes. Electron. Colloquium Comput. Complex., page 118, 2021. URL: https://eccc.weizmann.ac.il/report/2021/118.
  5. László Babai. Trading Group Theory for Randomness. In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 421-429. ACM, 1985. URL: https://doi.org/10.1145/22145.22192.
  6. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking Computations in Polylogarithmic Time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 21-31, 1991. URL: https://doi.org/10.1145/103418.103428.
  7. Alp Bassa, Peter Beelen, Arnaldo Garcia, and Henning Stichtenoth. An Improvement of the Gilbert–Varshamov Bound Over Nonprime Fields. IEEE Transactions on Information Theory, 60(7):3859-3861, 2014. URL: https://doi.org/10.1109/TIT.2014.2316531.
  8. Peter Beelen, Johan Rosenkilde, and Grigory Solomatov. Fast encoding of AG codes over c_ab curves. IEEE Trans. Inf. Theory, 67(3):1641-1655, 2021. URL: https://doi.org/10.1109/TIT.2020.3042248.
  9. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 14:1-14:17, 2018. Google Scholar
  10. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable Zero Knowledge with No Trusted Setup. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part III, volume 11694 of Lecture Notes in Computer Science, pages 701-732. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-26954-8_23.
  11. Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity Gaps for Reed-Solomon Codes. IACR Cryptol. ePrint Arch., 2020:654, 2020. Google Scholar
  12. Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Interactive Oracle Proofs with Constant Rate and Query Complexity. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 40:1-40:15, 2017. Google Scholar
  13. Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, and Nicholas Spooner. Linear-Size Constant-Query IOPs for Delegating Computation. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part II, volume 11892 of Lecture Notes in Computer Science, pages 494-521. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-36033-7_19.
  14. Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent Succinct Arguments for R1CS. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part I, volume 11476 of Lecture Notes in Computer Science, pages 103-128. Springer, 2019. Google Scholar
  15. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive Oracle Proofs. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II, pages 31-60, 2016. URL: https://doi.org/10.1007/978-3-662-53644-5_2.
  16. Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, pages 5:1-5:32, 2020. Google Scholar
  17. Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth. Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 320-329. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.42.
  18. Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. Worst-Case to Average Case Reductions for the Distance to a Code. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 24:1-24:23, 2018. Google Scholar
  19. Eli Ben-Sasson and Madhu Sudan. Short PCPs with Polylog Query Complexity. SIAM J. Comput., 38(2):551-607, 2008. URL: https://doi.org/10.1137/050646445.
  20. Jonathan Bootle, Alessandro Chiesa, and Siqi Liu. Zero-Knowledge Succinct Arguments with a Linear-Time Prover. IACR Cryptol. ePrint Arch., page 1527, 2020. URL: https://eprint.iacr.org/2020/1527.
  21. Alin Bostan and Eric Schost. Polynomial evaluation and interpolation on special sets of points. Journal of Complexity, 21(4):420-446, 2005. URL: https://doi.org/10.1016/j.jco.2004.09.009.
  22. Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. Fractal: Post-quantum and Transparent Recursive Proofs from Holography. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part I, volume 12105 of Lecture Notes in Computer Science, pages 769-793. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45721-1_27.
  23. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. URL: https://doi.org/10.1145/1236457.1236459.
  24. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 291-304. ACM, 1985. URL: https://doi.org/10.1145/22145.22178.
  25. Valerii Denisovich Goppa. Codes associated with divisors. Problemy Peredachi Informatsii, 13(1):33-39, 1977. Google Scholar
  26. J. W. P. Hirschfeld, G. Korchmáros, and F. Torres. Algebraic Curves over a Finite Field. Princeton University Press, Princeton, 25 Mar. 2013. URL: https://doi.org/10.1515/9781400847419.
  27. Chuangqiang Hu and Shudi Yang. Multi-point codes over Kummer extensions. Designs, Codes and Cryptography, 86:211-230, 2018. URL: https://doi.org/10.1007/s10623-017-0335-7.
  28. Yael Tauman Kalai and Ran Raz. Interactive PCP. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, volume 5126 of Lecture Notes in Computer Science, pages 536-547. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70583-3_44.
  29. Ernst Kani. The Galois-module structure of the space of holomorphic differentials of a curve. Journal für die reine und angewandte Mathematik, 367:187-206, 1986. URL: https://doi.org/10.1515/crll.1986.367.187.
  30. Assimakis Kattis, Konstantin Panarin, and Alexander Vlasov. RedShift: Transparent SNARKs from List Polynomial Commitment IOPs. IACR Cryptol. ePrint Arch., 2019:1400, 2019. URL: https://eprint.iacr.org/2019/1400.
  31. Joe Kilian. A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract). In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 723-732. ACM, 1992. URL: https://doi.org/10.1145/129712.129782.
  32. Gilles Lachaud. Sommes d'Eisenstein et nombre de points de certaines courbes algébriques sur les corps finis. C. R. Acad. Sci. Paris, 305, January 1987. Google Scholar
  33. Gilles Lachaud. Artin-Schreier curves, exponential sums, and coding theory. Theoretical Computer Science, 94(2):295-310, 1992. URL: https://doi.org/10.1016/0304-3975(92)90040-M.
  34. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic Methods for Interactive Proof Systems. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pages 2-10. IEEE Computer Society, 1990. URL: https://doi.org/10.1109/FSCS.1990.89518.
  35. Hiren Maharaj. Code Construction on Fiber Products of Kummer Covers. Information Theory, IEEE Transactions on, 50:2169-2173, October 2004. URL: https://doi.org/10.1109/TIT.2004.833356.
  36. Ariane M. Masuda, Luciane Quoos, and Alonso Sepúlveda. One- and Two-Point Codes over Kummer Extensions. IEEE Transactions on Information Theory, 62(9):4867-4872, 2016. URL: https://doi.org/10.1109/TIT.2016.2583437.
  37. Or Meir. IP = PSPACE Using Error-Correcting Codes. SIAM J. Comput., 42(1):380-403, 2013. URL: https://doi.org/10.1137/110829660.
  38. Silvio Micali. Computationally-Sound Proofs. In Johann A. Makowsky and Elena V. Ravve, editors, Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic, Logic Colloquium 1995, Haifa, Israel, August 9-18, 1995, volume 11 of Lecture Notes in Logic, pages 214-268. Springer, 1995. URL: https://doi.org/10.1007/978-3-662-22108-2_13.
  39. Thilo Mie. Short PCPPs Verifiable in Polylogarithmic Time with O(1) Queries. Annals of Mathematics and Artificial Intelligence, 56(3–4):313-338, August 2009. URL: https://doi.org/10.1007/s10472-009-9169-y.
  40. Carlos Munuera and Ruud Pellikaan. Equality of geometric Goppa codes and equivalence of divisors. Journal of Pure and Applied Algebra, 90(3):229-252, 1993. URL: https://doi.org/10.1016/0022-4049(93)90043-S.
  41. Ruud Pellikaan, Ba zhong Shen, and Gerhard J. M. van Wee. Which linear codes are algebraic-geometric? IEEE Trans. Inf. Theory, 37:583-602, 1991. URL: https://doi.org/10.1109/18.79915.
  42. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 49-62. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897652.
  43. Noga Ron-Zewi and Ron D. Rothblum. Local Proofs Approaching the Witness Length [Extended Abstract]. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 846-857. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00083.
  44. StarkWare. ethSTARK Documentation. IACR Cryptol. ePrint Arch., page 582, 2021. URL: https://eprint.iacr.org/2021/582.
  45. Henning Stichtenoth. Algebraic Function Fields and Codes. Springer Publishing Company, Incorporated, 2nd edition, 2008. Google Scholar
  46. Saeed Tafazolian and Fernando Torres. On the curve yⁿ = x^m + x over finite fields. Journal of Number Theory, 145:51-66, 2014. URL: https://doi.org/10.1016/j.jnt.2014.05.019.
  47. M. A. Tsfasman, S. G. Vlăduţ, and Th. Zink. Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound. Math. Nachr., 109:21-28, 1982. URL: https://doi.org/10.1002/mana.19821090103.
  48. Michael Tsfasman, Serge Vladut, and Dmitry Nogin. Algebraic Geometric Codes: Basic Notions. American Mathematical Society, USA, 2007. Google Scholar
  49. Jiaheng Zhang, Tiancheng Xie, Yupeng Zhang, and Dawn Song. Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof. In 2020 IEEE Symposium on Security and Privacy, SP 2020, San Francisco, CA, USA, May 18-21, 2020, pages 859-876. IEEE, 2020. URL: https://doi.org/10.1109/SP40000.2020.00052.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact