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]
[AGG+25] Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami, Ray Li, Zihan Zhang. Random Reed-Solomon codes achieve list-decoding capacity with linear-sized alphabets. Advances in Combinatorics, 2025. doi:10.19086/aic.2025.8. [1] [2] [3]
[AGL23] Omar Alrabiah, Venkatesan Guruswami, Ray Li. AG codes have no list-decoding friends: approaching the generalized Singleton bound requires exponential alphabets. CoRR, 2023. arXiv:2308.13424, URL: https://arxiv.org/abs/2308.13424. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
[AGL24] Omar Alrabiah, Venkatesan Guruswami, Ray Li. Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC '24, 1458–1469. 2024. [1] [2] [3] [4] [5]
[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] [9]
[ABF26] Gal Arnon, Dan Boneh, Giacomo Fenzi. Open Problems in List Decoding and Correlated Agreement. Manuscript, accompanying the Ethereum Foundation Proximity Prize, 2026. URL: https://proximityprize.org/. [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] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96]
[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] [9] [10] [11] [12] [13]
[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] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44]
[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. [1]
[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.
[BSCH+25] Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, Shubhangi Saraf. On Proximity Gaps for Reed–Solomon Codes. Cryptology ePrint Archive, Paper 2025/2055, 2025. URL: https://eprint.iacr.org/2025/2055. [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]
[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] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103]
[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.
[BSGKS20] Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference, ITCS '20, 5:1–5:32. 2020. [1] [2] [3]
[BSKR06] Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan. Subspace polynomials and list decoding of Reed-Solomon codes. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 207–216. 2006. [1] [2] [3] [4] [5] [6]
[BSS08] Eli Ben-Sasson, Madhu Sudan. Short PCPs with polylog query complexity. SIAM Journal on Computing, 38(2):551–607, 2008. doi:10.1137/050646445, 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] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32]
[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.
[BCP+26] Joshua Brakensiek, Yeyuan Chen, Aaron Putterman, Zihan Zhang, Kai Zhe Zheng. Algorithmic List Decoding of Reed–Solomon Codes up to Capacity in the Low-Rate Regime. Electronic Colloquium on Computational Complexity, Report TR26-164, 2026. URL: https://eccc.weizmann.ac.il/report/2026/164/. [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]
[BDG24] Joshua Brakensiek, Manik Dhar, Sivakanth Gopi. Improved field size bounds for higher order MDS codes. IEEE Transactions on Information Theory, 70(10):6950–6960, 2024. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
[BGM23] Joshua Brakensiek, Sivakanth Gopi, Visu Makam. Generic Reed-Solomon codes achieve list-decoding capacity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC '23, 1488–1501. 2023. [1] [2] [3]
[BCFW25a] Benedikt Bünz, Alessandro Chiesa, Giacomo Fenzi, William Wang. Linear time accumulation schemes. Cryptology ePrint Archive, Paper 2025/753, 2025. URL: https://eprint.iacr.org/2025/753. [1]
[BCFW25b] 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.
[CZ25] Yeyuan Chen, Zihan Zhang. Explicit folded Reed-Solomon and multiplicity codes achieve relaxed generalized Singleton bounds. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC '25, 1–12. ACM, 2025. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23]
[CW07] Qi Cheng, Daqing Wan. On the list and bounded distance decodability of Reed-Solomon codes. SIAM Journal on Computing, 37(1):195–209, 2007. doi:10.1137/S0097539705447335, URL: https://doi.org/10.1137/S0097539705447335. [1] [2]
[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.
[CY24] Alessandro Chiesa, Eylon Yogev. Building Cryptographic Proofs from Hash Functions. 2024. URL: https://github.com/hash-based-snargs-book.
[CS25] Elizabeth Crites, Alistair Stewart. On Reed–Solomon Proximity Gaps Conjectures. Cryptology ePrint Archive, Paper 2025/2046, 2025. URL: https://eprint.iacr.org/2025/2046. [1] [2] [3] [4] [5] [6] [7]
[DKT26] Quang Dao, Scott Duke Kominers, Justin Thaler. Reed–Solomon Codes Beyond Johnson: Efficient Decoding and Smaller Cryptographic Proofs. Cryptology ePrint Archive, Paper 2026/2056, 2026. URL: https://eprint.iacr.org/2026/2056. [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]
[DP24] Benjamin E Diamond, Jim Posen. Polylogarithmic proofs for multilinears over binary towers. Cryptology ePrint Archive, 2024. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23]
[DG25a] Benjamin E. Diamond, Angus Gruen. On the distribution of the distances of random words. Cryptology ePrint Archive, Paper 2025/2010, 2025. URL: https://eprint.iacr.org/2025/2010. [1] [2] [3] [4] [5]
[DG25b] 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] [2]
[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. [1]
[Eli57] Peter Elias. List decoding for noisy channels. Technical Report, Research Laboratory of Electronics, Massachusetts Institute of Technology, 1957. [1] [2] [3] [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] [8] [9] [10] [11] [12]
[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]
[GCXK25] Yiwen Gao, Dongliang Cai, Yang Xu, Haibin Kan. From List-Decodability to Proximity Gaps. Cryptology ePrint Archive, Paper 2025/870, 2025. URL: https://eprint.iacr.org/2025/870. [1] [2]
[GKL24] Yiwen Gao, Haibin Kan, Yuan Li. Linear Proximity Gap for Linear Codes within the 1.5 Johnson Bound. Cryptology ePrint Archive, Paper 2024/1810, 2024. URL: https://eprint.iacr.org/2024/1810. [1] [2]
[GGR11] Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra. List Decoding Tensor Products and Interleaved Codes. SIAM Journal on Computing, 40(5):1432–1462, 2011. doi:10.1137/090778280. [1]
[GG25] Rohan Goyal, Venkatesan Guruswami. Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes. Cryptology ePrint Archive, Paper 2025/2054, 2025. URL: https://eprint.iacr.org/2025/2054. [1] [2] [3] [4] [5]
[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]
[GZ23] Zeyu Guo, Zihan Zhang. Randomly punctured Reed-Solomon codes achieve the list decoding capacity over polynomial-size alphabets. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science, FOCS '23, 164–176. 2023. [1] [2] [3]
[GHSZ02] Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory, 48(5):1021–1034, 2002. doi:10.1109/18.995539, URL: https://doi.org/10.1109/18.995539. [1] [2] [3] [4] [5]
[GK16] Venkatesan Guruswami, Swastik Kopparty. Explicit subspace designs. Combinatorica, 36(2):161–185, 2016. [1] [2] [3]
[GLM+22] Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters. Bounds for list-decoding and list-recovery of random linear codes. IEEE Transactions on Information Theory, 68(2):923–939, 2022. doi:10.1109/TIT.2021.3127126, URL: https://doi.org/10.1109/TIT.2021.3127126. [1] [2] [3] [4] [5]
[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]
[GR08] Venkatesan Guruswami, Atri Rudra. Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy. IEEE Transactions on Information Theory, 54(1):135–150, 2008. [1] [2]
[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] [3]
[GW13] Venkatesan Guruswami, Carol Wang. Linear-Algebraic List Decoding for Variants of Reed-Solomon Codes. IEEE Transactions on Information Theory, 59(6):3257–3268, 2013. doi:10.1109/TIT.2013.2246813, URL: https://doi.org/10.1109/TIT.2013.2246813. [1]
[GX13] Venkatesan Guruswami, Chaoping Xing. List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. In Proceedings of the 45th Annual ACM SIGACT Symposium on Theory of Computing, STOC '13, 843–852. ACM, 2013. [1]
[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]
[HMZ25] Mi-Ying Miryam Huang, Xinyu Mao, Jiapeng Zhang. Sublinear Proofs over Polynomial Rings. Cryptology ePrint Archive, Paper 2025/199, 2025. URL: https://eprint.iacr.org/2025/199. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
[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. [1] [2] [3] [4]
[Joh62] Selmer M. Johnson. A new upper bound for error-correcting codes. IRE Transactions on Information Theory, 8(3):203–207, 1962. [1]
[JH01] Jørn Justesen, Tom Høholdt. Bounds on list decoding of MDS codes. IEEE Transactions on Information Theory, 47(4):1604–1609, 2001. doi:10.1109/18.923744, URL: https://doi.org/10.1109/18.923744. [1] [2] [3] [4] [5] [6]
[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]
[Kop15] Swastik Kopparty. List-Decoding Multiplicity Codes. Theory of Computing, 11(5):149–182, 2015. URL: https://theoryofcomputing.org/articles/v011a005/. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
[KSY14] Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin. High-rate codes with sublinear-time decoding. Journal of the ACM, 61(5):28:1–28:20, 2014. Preliminary version appeared in STOC '11. [1]
[KP23] Abhiram Kothapalli, Bryan Parno. Algebraic reductions of knowledge. In Annual International Cryptology Conference, 669–701. Springer, 2023.
[KKH26] Dmitry Krachun, Stepan Kazanin, Ulrich Haböck. Failure of Proximity Gaps Close to Capacity. Cryptology ePrint Archive, Paper 2026/782, 2026. URL: https://eprint.iacr.org/2026/782. [1] [2] [3] [4] [5] [6] [7] [8]
[Lan02] Serge Lang. Algebra. Revised Third edition. Volume 211 of Graduate Texts in Mathematics. Springer, 2002. [1] [2]
[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] [3]
[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] [16] [17] [18] [19] [20] [21] [22] [23] [24]
[MWS77] Florence Jessie MacWilliams, Neil James Alexander Sloane. The Theory of Error-Correcting Codes. Volume 16. Elsevier, 1977. [1] [2] [3] [4] [5] [6]
[Mic07] Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity, 16(4):365–411, 2007. [1] [2] [3] [4] [5]
[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] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214]
[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] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41]
[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.
[ST20] Chong Shangguan, Itzhak Tamo. Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC '20, 538–551. 2020. [1] [2] [3] [4] [5] [6] [7] [8]
[Spi95] Daniel Alan Spielman. Computationally efficient error-correcting codes and holographic proofs. PhD thesis, Massachusetts Institute of Technology, 1995. [1]
[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.