References

[Ajt96] Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC), 99–108. 1996. [1] [2] [3] [4] [5] [6] [7] [8]
[AHIV17] Scott Ames, Carmit Hazay, Yuval Ishai, Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. In Proceedings of the 2017 acm sigsac conference on computer and communications security, 2087–2104. 2017. [1] [2] [3] [4] [5] [6] [7] [8]
[ACFY24a] Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev. STIR: Reed-Solomon proximity testing with fewer queries. In Annual International Cryptology Conference, 380–413. Springer, 2024. [1] [2] [3] [4] [5] [6] [7] [8]
[ACFY24b] Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev. WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification. Cryptology ePrint Archive, Paper 2024/1586, 2024. URL: https://eprint.iacr.org/2024/1586. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30]
[ACFY25a] Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev. WHIR: Reed–Solomon proximity testing with super-fast verification. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, 214–243. Springer, 2025.
[ACFY25b] Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev. WHIR: Reed–Solomon proximity testing with super-fast verification. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, 214–243. Springer, 2025.
[BMMS25] Anubhav Baweja, Pratyush Mishra, Tushar Mopuri, Matan Shtepel. FICS and FACS: Fast IOPPs and Accumulation via Code-Switching. Cryptology ePrint Archive, 2025.
[BSCI+20] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf. Proximity Gaps for Reed-Solomon Codes. Cryptology ePrint Archive, Paper 2020/654, 2020. URL: https://eprint.iacr.org/2020/654. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76]
[BSCI+23] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf. Proximity gaps for Reed–Solomon codes. Journal of the ACM, 70(5):1–57, 2023.
[BSCS16a] Eli Ben-Sasson, Alessandro Chiesa, Nicholas Spooner. Interactive Ooracle Proofs. In Theory of Cryptography: 14th International Conference, TCC 2016-B, Beijing, China, October 31-November 3, 2016, Proceedings, Part II 14, 31–60. Springer, 2016. [1] [2]
[BSCS16b] Eli Ben-Sasson, Alessandro Chiesa, 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 14, 31–60. Springer, 2016.
[BSS08] Eli Ben-Sasson, Madhu Sudan. Short PCPs with polylog query complexity. SIAM Journal on Computing, 38(2):551–607, 2008. URL: https://people.csail.mit.edu/madhu/papers/2005/rspcpp-full.pdf.
[BCGM25] Sarah Bordage, Alessandro Chiesa, Ziyi Guan, Ignacio Manzur. All Polynomial Generators Preserve Distance with Mutual Correlated Agreement. Cryptology ePrint Archive, Paper 2025/2051, 2025. URL: https://eprint.iacr.org/2025/2051. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
[BBS24] Azucena Garvia Bosshard, Jonathan Bootle, Christoph Sprenger. Formal Verification of the Sumcheck Protocol. In 2024 IEEE 37th Computer Security Foundations Symposium (CSF), 205–219. IEEE Computer Society, 2024. [1]
[BCG+18] Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra, Howard Wu. Zexe: Enabling Decentralized Private Computation. Cryptology ePrint Archive, Paper 2018/962, 2018. doi:10.1109/SP40000.2020.00050, URL: https://eprint.iacr.org/2018/962.
[BCFW25] Benedikt Bünz, Alessandro Chiesa, Giacomo Fenzi, William Wang. Linear-Time Accumulation Schemes. Cryptology ePrint Archive, 2025.
[BFS20] Benedikt Bünz, Ben Fisch, Alan Szepieniec. Transparent SNARKs from DARK compilers. In 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 39, 677–706. Springer, 2020.
[BMNW24] Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, William Wang. Arc: Accumulation for Reed–Solomon Codes. Cryptology ePrint Archive, 2024.
[CGKY25] Alessandro Chiesa, Ziyi Guan, Christian Knabenhans, Zihan Yu. On the Fiat-Shamir Security of Succinct Arguments from Functional Commitments. Cryptology ePrint Archive, Paper 2025/902, 2025. URL: https://eprint.iacr.org/2025/902. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
[CHM+20] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, Nicholas Ward. Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In 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 39, 738–768. Springer, 2020.
[CHM+18] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, Nicholas Ward. Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. Cryptology ePrint Archive, Paper 2018/962, 2018. URL: https://eprint.iacr.org/2018/962.
[CY24] Alessandro Chiesa, Eylon Yogev. Building Cryptographic Proofs from Hash Functions. 2024. URL: https://github.com/hash-based-snargs-book.
[DP24] Benjamin E Diamond, Jim Posen. Polylogarithmic proofs for multilinears over binary towers. Cryptology ePrint Archive, 2024. [1] [2] [3] [4]
[DG25] Benjamin E. Diamond, Angus Gruen. Proximity Gaps in Interleaved Codes. IACR Communications in Cryptology, 2025. doi:10.62056/a0ljbkrz, URL: https://cic.iacr.org/p/1/4/8. [1] [2] [3]
[DP23] Benjamin E. Diamond, Jim Posen. Succinct Arguments over Towers of Binary Fields. Cryptology ePrint Archive, Paper 2023/1784, 2023. doi:10.1007/978-3-031-91134-7_4, URL: https://eprint.iacr.org/2023/1784. [1]
[DP25] Benjamin E. Diamond, Jim Posen. Succinct Arguments over Towers of Binary Fields. In Advances in Cryptology – EUROCRYPT 2025: 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4–8, 2025, Proceedings, Part IV, 93–122. Berlin, Heidelberg, 2025. Springer-Verlag. doi:10.1007/978-3-031-91134-7_4, URL: https://doi.org/10.1007/978-3-031-91134-7_4.
[FP97] J.L. Fan, C. Paar. On efficient inversion in tower fields of characteristic two. In Proceedings of IEEE International Symposium on Information Theory, 20-. 1997. doi:10.1109/ISIT.1997.612935.
[FMN24] Giacomo Fenzi, Hossein Moghaddas, Ngoc Khanh Nguyen. Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency. Journal of Cryptology, 37(3):31, 2024. doi:10.1007/s00145-024-09511-8, URL: https://eprint.iacr.org/2023/846. [1] [2] [3] [4] [5] [6] [7]
[GWC19] Ariel Gabizon, Zachary J Williamson, Oana Ciobotaru. Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, 2019. URL: https://eprint.iacr.org/2019/953.pdf. [1] [2]
[GKR+23] Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, Markus Schofnegger. Poseidon2: A Faster Version of the Poseidon Hash Function. Cryptology ePrint Archive, Paper 2023/323, 2023. URL: https://eprint.iacr.org/2023/323. [1]
[Go07] Venkatesan Guruswami, others. Algorithmic results in list decoding. Foundations and Trends\textregistered in Theoretical Computer Science, 2(2):107–195, 2007. [1] [2] [3]
[GRS12] Venkatesan Guruswami, Atri Rudra, Madhu Sudan. Essential coding theory. Draft available at http://www. cse. buffalo. edu/atri/courses/coding-theory/book, 2012. [1] [2]
[Hab22] Ulrich Haböck. A summary on the FRI low degree test. Cryptology ePrint Archive, Paper 2022/1216, 2022. URL: https://eprint.iacr.org/2022/1216. [1] [2]
[JM24] Joseph Jaeger, Deep Inder Mohan. Generic and algebraic computation models: When AGM proofs transfer to the GGM. In Annual International Cryptology Conference, 14–45. Springer, 2024. URL: https://link.springer.com/content/pdf/10.1007/978-3-031-68388-6_2. [1] [2]
[Jo26] Sunghyeon Jo. Interleaving Stability for Mutual Correlated Agreement and Curve Decodability. Cryptology ePrint Archive, Paper 2026/891, 2026. URL: https://eprint.iacr.org/2026/891.
[KZG10a] Aniket Kate, Gregory M. Zaverucha, Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. In Advances in Cryptology – ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science, 177–194. Springer, 2010. doi:10.1007/978-3-642-17373-8_11, URL: https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf. [1]
[KZG10b] Aniket Kate, Gregory M. Zaverucha, Ian Goldberg. Polynomial Commitments. Technical Report CACR 2010-10, Centre for Applied Cryptographic Research, University of Waterloo, 2010. URL: https://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf. [1]
[KP23] Abhiram Kothapalli, Bryan Parno. Algebraic reductions of knowledge. In Annual International Cryptology Conference, 669–701. Springer, 2023.
[Lan02] Serge Lang. Algebra. Revised Third edition. Volume 211 of Graduate Texts in Mathematics. Springer, 2002. [1]
[LCH14] Sian-Jheng Lin, Wei-Ho Chung, Yunghsiang S Han. Novel polynomial basis and its application to reed-solomon erasure codes. In 2014 ieee 55th annual symposium on foundations of computer science, 316–325. IEEE, 2014. [1]
[LPS24] Helger Lipmaa, Roberto Parisella, Janno Siim. On Knowledge-Soundness of Plonk in ROM from Falsifiable Assumptions. Cryptology ePrint Archive, Paper 2024/994, 2024. URL: https://eprint.iacr.org/2024/994. [1] [2]
[LFKN92] Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, Oct 1992. doi:10.1145/146585.146605, URL: https://doi.org/10.1145/146585.146605. [1]
[LNP22] Vadim Lyubashevsky, Ngoc Khanh Nguyen, Maxime Plançon. Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General. In Advances in Cryptology – CRYPTO 2022, volume 13508 of Lecture Notes in Computer Science, 71–101. Springer, 2022. [1] [2]
[LS18] Vadim Lyubashevsky, Gregor Seiler. Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs. In Advances in Cryptology – EUROCRYPT 2018, volume 10820 of Lecture Notes in Computer Science, 204–224. Springer, 2018. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
[Mic07] Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity, 16(4):365–411, 2007. [1] [2] [3]
[NORZ26] Ngoc Khanh Nguyen, George O'Rourke, Jiapeng Zhang. Hachi: Efficient Lattice-Based Multilinear Polynomial Commitments over Extension Fields. Cryptology ePrint Archive, Paper 2026/156, 2026. URL: https://eprint.iacr.org/2026/156. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57]
[NS24] Ngoc Khanh Nguyen, Gregor Seiler. Greyhound: Fast Polynomial Commitments from Lattices. In Advances in Cryptology – CRYPTO 2024, volume 14929 of Lecture Notes in Computer Science, 243–275. Springer, 2024. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25]
[PS94] Alexander Polishchuk, Daniel A Spielman. Nearly-linear size holographic proofs. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, 194–203. 1994. [1] [2] [3]
[Set20] Srinath Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In Annual International Cryptology Conference, 704–737. Springer, 2020.
[Spi95] Daniel Alan Spielman. Computationally efficient error-correcting codes and holographic proofs. PhD thesis, Massachusetts Institute of Technology, 1995. [1]
[Sud05] Madhu Sudan. Reed-Solomon codes and polynomial reconstruction. Available at https://people.csail.mit.edu/madhu/papers/2005/rspcpp-full.pdf, 2005.
[VzGG96] Joachim Von zur Gathen, Jürgen Gerhard. Arithmetic and factorization of polynomial over F2 (extended abstract). In Proceedings of the 1996 international symposium on Symbolic and algebraic computation, 1–9. 1996. [1] [2] [3]
[WW23] Hoeteck Wee, David J. Wu. Succinct Vector, Polynomial, and Functional Commitments from Lattices. In Advances in Cryptology – EUROCRYPT 2023, volume 14006 of Lecture Notes in Computer Science, 385–416. Springer, 2023.
[Wie88] Doug Wiedemann. An Iterated Quadratic Extension of GF(2). The Fibonacci Quarterly, 26(4):290–295, 1988. doi:10.1080/00150517.1988.12429608, URL: https://doi.org/10.1080/00150517.1988.12429608, URL: https://doi.org/10.1080/00150517.1988.12429608.