{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T02:45:18Z","timestamp":1767321918022,"version":"3.48.0"},"publisher-location":"Cham","reference-count":47,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032105356","type":"print"},{"value":"9783032105363","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-10536-3_13","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T02:42:42Z","timestamp":1767321762000},"page":"339-368","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Accelerating Post-quantum Secure zkSNARKs by\u00a0Optimizing Additive FFT"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2631-1777","authenticated-orcid":false,"given":"Mohammadtaghi","family":"Badakhshan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4643-5117","authenticated-orcid":false,"given":"Susanta","family":"Samanta","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2684-9259","authenticated-orcid":false,"given":"Guang","family":"Gong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"issue":"11","key":"13_CR1","doi-asserted-by":"publisher","first-page":"3379","DOI":"10.1007\/s10623-023-01222-8","volume":"91","author":"S Ames","year":"2023","unstructured":"Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. Des. Codes Crypt. 91(11), 3379\u20133424 (2023)","journal-title":"Des. Codes Crypt."},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Baum, C., et al.: Publicly verifiable zero-knowledge and post-quantum signatures from VOLE-in-the-head. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology \u2013 CRYPTO 2023, pp. 581\u2013615. Springer Nature Switzerland, Cham (2023)","DOI":"10.1007\/978-3-031-38554-4_19"},{"key":"13_CR3","unstructured":"Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast reed-Solomon interactive oracle proofs of proximity. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, pp. 14:1\u201314:17. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2018)"},{"key":"13_CR4","unstructured":"Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Paper 2018\/046 (2018)"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Carmon, D., Kopparty, S., Levit, D.: Scalable and transparent proofs over all large fields, via elliptic curves. In: Kiltz, E., Vaikuntanathan, V. (eds.) Theory of Cryptography, pp. 467\u2013496. Springer, Cham (2022)","DOI":"10.1007\/978-3-031-22318-1_17"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Carmon, D., Kopparty, S., Levit, D.: Elliptic curve fast Fourier transform (ECFFT) part I: low-degree extension in time $$o(n \\log n)$$ over all finite fields. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 700\u2013737 (2023)","DOI":"10.1137\/1.9781611977554.ch30"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-319-70503-3_6","volume-title":"Theory of Cryptography","author":"E Ben-Sasson","year":"2017","unstructured":"Ben-Sasson, E., Chiesa, A., Forbes, M.A., Gabizon, A., Riabzev, M., Spooner, N.: Zero knowledge protocols from succinct constraint detection. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 172\u2013206. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_6"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 459\u2013474 (2014)","DOI":"10.1109\/SP.2014.36"},{"key":"13_CR9","unstructured":"Ben-Sasson, E., et al.: Libiop: a C++ library for zero knowledge proofs. https:\/\/github.com\/scipr-lab\/libiop. Accessed 10 Jan 2025"},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-030-17653-2_4","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"E Ben-Sasson","year":"2019","unstructured":"Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: transparent succinct arguments for R1CS. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 103\u2013128. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17653-2_4"},{"key":"13_CR11","unstructured":"Ben-Sasson, E., et al.: libff: C++ library for finite fields and elliptic curves. https:\/\/github.com\/scipr-lab\/libff. Accessed 10 Jan 2025"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-319-13051-4_6","volume-title":"Selected Areas in Cryptography \u2013 SAC 2014","author":"DJ Bernstein","year":"2014","unstructured":"Bernstein, D.J., Chou, T.: Faster binary-field multiplication and faster binary-field MACs. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 92\u2013111. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-13051-4_6"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-40349-1_15","volume-title":"Cryptographic Hardware and Embedded Systems - CHES 2013","author":"DJ Bernstein","year":"2013","unstructured":"Bernstein, D.J., Chou, T., Schwabe, P.: McBits: fast constant-time code-based cryptography. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 250\u2013272. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40349-1_15"},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-030-51280-4_23","volume-title":"Financial Cryptography and Data Security","author":"B B\u00fcnz","year":"2020","unstructured":"B\u00fcnz, B., Agrawal, S., Zamani, M., Boneh, D.: Zether: towards privacy in a smart contract world. In: Bonneau, J., Heninger, N. (eds.) FC 2020. LNCS, vol. 12059, pp. 423\u2013443. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51280-4_23"},{"issue":"2","key":"13_CR15","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0097-3165(89)90020-4","volume":"50","author":"DG Cantor","year":"1989","unstructured":"Cantor, D.G.: On arithmetical algorithms over finite fields. J. Comb. Theory Ser. A 50(2), 285\u2013300 (1989)","journal-title":"J. Comb. Theory Ser. A"},{"key":"13_CR16","unstructured":"Chaliasos, S., Reif, I., Torralba-Agell, A., Ernstberger, J., Kattis, A., Livshits, B.: Analyzing and benchmarking ZK-rollups. In: B\u00f6hme, R., Kiffer, L. (eds.) 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 316, pp. 6:1\u20136:24. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2024)"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, pp. 1825\u20131842. Association for Computing Machinery, New York, NY, USA (2017)","DOI":"10.1145\/3133956.3133997"},{"key":"13_CR18","unstructured":"Chen, M.-S., et al.: Preon: zk-SNARK based Signature Scheme. Technical report, NIST (2023)"},{"key":"13_CR19","unstructured":"Chen, M.-S., Cheng, C.-M., Kuo, P.-C., Li, W.-D., Yang, B.-Y.: Faster multiplication for long binary polynomials. arXiv:\u00a01708.09746 (2018). https:\/\/arxiv.org\/abs\/1708.09746"},{"key":"13_CR20","unstructured":"Chen, M.-S., Cheng, C.-M., Kuo, P.-C., Li, W.-D., Yang, B.-Y.: Multiplying Boolean polynomials with Frobenius partitions in additive fast Fourier transform. arXiv:\u00a01803.11301 (2018). https:\/\/arxiv.org\/abs\/1803.11301"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1007\/978-3-030-45721-1_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"A Chiesa","year":"2020","unstructured":"Chiesa, A., Ojha, D., Spooner, N.: Fractal: post-quantum and transparent recursive proofs from holography. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 769\u2013793. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45721-1_27"},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1016\/j.jsc.2020.10.002","volume":"104","author":"N Coxon","year":"2021","unstructured":"Coxon, N.: Fast transforms over finite fields of characteristic two. J. Symb. Comput. 104, 824\u2013854 (2021)","journal-title":"J. Symb. Comput."},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Diamond, B.E., Posen, J.: Succinct arguments over towers of binary fields. In: Fehr, S., Fouque, P.-A. (eds.) Advances in Cryptology \u2013 EUROCRYPT 2025, pp. 93\u2013122. Springer, Cham (2025)","DOI":"10.1007\/978-3-031-91134-7_4"},{"issue":"10","key":"13_CR24","doi-asserted-by":"publisher","first-page":"589","DOI":"10.2307\/2304500","volume":"54","author":"NJ Fine","year":"1947","unstructured":"Fine, N.J.: Binomial coefficients modulo a prime. Am. Math. Mon. 54(10), 589\u2013592 (1947)","journal-title":"Am. Math. Mon."},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Fu, S., Gong, G.: Polaris: transparent succinct zero-knowledge arguments for R1CS with efficient verifier. In: Proceedings on Privacy Enhancing Technologies (2022)","DOI":"10.2478\/popets-2022-0027"},{"issue":"12","key":"13_CR26","doi-asserted-by":"publisher","first-page":"6265","DOI":"10.1109\/TIT.2010.2079016","volume":"56","author":"S Gao","year":"2010","unstructured":"Gao, S., Mateer, T.: Additive fast Fourier transforms over finite fields. IEEE Trans. Inf. Theory 56(12), 6265\u20136272 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"von\u00a0zur Gathen, J., Gerhard, J.: Arithmetic and factorization of polynomial over $$\\mathbb{F}_2$$ (extended abstract). In: Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC 1996, pp. 1\u20139. Association for Computing Machinery, New York, NY, USA (1996)","DOI":"10.1145\/236869.236882"},{"key":"13_CR28","unstructured":"Google Inc. and contributors. Benchmark - a microbenchmark support library. https:\/\/github.com\/google\/benchmark. Accessed 10 Jan 2025"},{"key":"13_CR29","unstructured":"Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: POSEIDON: a new hash function for Zero-Knowledge proof systems. In: 30th USENIX Security Symposium (USENIX Security 21), pp. 519\u2013535. USENIX Association, August 2021"},{"issue":"4","key":"13_CR30","doi-asserted-by":"publisher","first-page":"800","DOI":"10.46586\/tches.v2022.i4.800-827","volume":"2022","author":"Q Guo","year":"2022","unstructured":"Guo, Q., Johansson, A., Johansson, T.: A key-recovery side-channel attack on classic McEliece implementations. IACR Trans. Cryptograph. Hardware Embedded Syst. 2022(4), 800\u2013827 (2022)","journal-title":"IACR Trans. Cryptograph. Hardware Embedded Syst."},{"key":"13_CR31","unstructured":"Jandhyala, T.: Air-FRI: acceleration of the FRI protocol on the GPU for low-degree polynomial testing in zk-SNARK applications. Master\u2019s thesis, University of Waterloo, Canada (2024)"},{"key":"13_CR32","doi-asserted-by":"crossref","unstructured":"Katz, J., Kolesnikov, V., Wang, X.: Improved non-interactive zero knowledge with applications to post-quantum signatures. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, pp. 525\u2013537. Association for Computing Machinery, New York, NY, USA (2018)","DOI":"10.1145\/3243734.3243805"},{"key":"13_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1007\/978-3-030-64837-4_29","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2020","author":"N Lahr","year":"2020","unstructured":"Lahr, N., Niederhagen, R., Petri, R., Samardjiska, S.: Side channel information set decoding using iterative chunking. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 881\u2013910. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64837-4_29"},{"key":"13_CR34","doi-asserted-by":"crossref","unstructured":"Li, D., Pakala, A., Yang, K.: MeNTT: a compact and efficient processing-in-memory number theoretic transform (NTT) accelerator. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 30(5), 579\u2013588 (2022)","DOI":"10.1109\/TVLSI.2022.3151321"},{"key":"13_CR35","doi-asserted-by":"crossref","unstructured":"Li, W.-D., Chen, M.-S., Kuo, P.-C., Cheng, C.-M., Yang, B.-Y.: Frobenius additive fast Fourier transform. In: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2018, pp. 263\u2013270 (2018)","DOI":"10.1145\/3208976.3208998"},{"key":"13_CR36","doi-asserted-by":"crossref","unstructured":"Lin, S.-J., Al-Naffouri, T.Y., Han, Y.S.: FFT algorithm for binary extension finite fields and its application to Reed\u2013Solomon codes. IEEE Trans. Inf. Theory 62(10), 5343\u20135358 (2016)","DOI":"10.1109\/TIT.2016.2600417"},{"key":"13_CR37","doi-asserted-by":"crossref","unstructured":"Lin, S.-J., Al-Naffouri, T.Y., Han, Y.S., Chung, W.-H.: Novel polynomial basis with fast fourier transform and its application to Reed\u2013Solomon erasure codes. IEEE Trans. Inf. Theory 62(11), 6284\u20136299 (2016)","DOI":"10.1109\/TIT.2016.2608892"},{"key":"13_CR38","doi-asserted-by":"crossref","unstructured":"Lin, S.-J., Chung, W.-H., Han, Y.S.: Novel polynomial basis and its application to Reed-Solomon erasure codes. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 316\u2013325 (2014)","DOI":"10.1109\/FOCS.2014.41"},{"issue":"4","key":"13_CR39","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/2369373","volume":"1","author":"E Lucas","year":"1878","unstructured":"Lucas, E.: Th\u00e9orie des fonctions num\u00e9riques simplement p\u00e9riodiques. Am. J. Math. 1(4), 289\u2013321 (1878)","journal-title":"Am. J. Math."},{"issue":"2","key":"13_CR40","doi-asserted-by":"publisher","first-page":"358","DOI":"10.46586\/tches.v2023.i2.358-380","volume":"2023","author":"G Luo","year":"2023","unstructured":"Luo, G., Shihui, F., Gong, G.: Speeding up multi-scalar multiplication over fixed points towards efficient zkSNARKs. IACR Trans. Cryptograph. Hardware Embedded Syst. 2023(2), 358\u2013380 (2023)","journal-title":"IACR Trans. Cryptograph. Hardware Embedded Syst."},{"key":"13_CR41","unstructured":"Mateer, T.: Fast Fourier transform algorithms with applications. Ph.D. thesis. Clemson University (2008). https:\/\/open.clemson.edu\/all_dissertations\/231\/"},{"key":"13_CR42","unstructured":"National Institute of\u00a0Standards and Technology: Post-Quantum Cryptography: Standardization Process (2023). https:\/\/csrc.nist.gov\/projects\/pqc-dig-sig\/round-1-additional-signatures. Accessed 10 Jan 2025"},{"key":"13_CR43","doi-asserted-by":"crossref","unstructured":"Steffen, S., Bichsel, B., Baumgartner, R., Vechev, M.: ZeeStar: private smart contracts by homomorphic encryption and zero-knowledge proofs. In: 2022 IEEE Symposium on Security and Privacy (SP), pp. 179\u2013197 (2022)","DOI":"10.1109\/SP46214.2022.9833732"},{"key":"13_CR44","doi-asserted-by":"crossref","unstructured":"Thibault, L.T., Sarry, T., Hafid, A.S.: Blockchain scaling using rollups: a comprehensive survey. IEEE Access 10, 93039\u201393054 (2022)","DOI":"10.1109\/ACCESS.2022.3200051"},{"key":"13_CR45","doi-asserted-by":"crossref","unstructured":"Van\u00a0Nieuwpoort, R.V., Wrzesi\u0144ska, G., Jacobs, C.J.H., Bal, H.E.: Satin: a high-level and efficient grid programming model. ACM Trans. Program. Lang. Syst. 32(3) (2010)","DOI":"10.1145\/1709093.1709096"},{"issue":"3","key":"13_CR46","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1109\/49.1926","volume":"6","author":"Y Wang","year":"1988","unstructured":"Wang, Y., Zhu, X.: A fast algorithm for the Fourier transform over finite fields and its VLSI implementation. IEEE J. Sel. Areas Commun. 6(3), 572\u2013577 (1988)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"13_CR47","unstructured":"Xiong, A.L., et al.: VeriZexe: decentralized private computation with universal setup. In: 32nd USENIX Security Symposium (USENIX Security 23), pp. 4445\u20134462. USENIX Association, Anaheim, CA, August 2023"}],"container-title":["Lecture Notes in Computer Science","Selected Areas in Cryptography \u2013 SAC 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-10536-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T02:42:44Z","timestamp":1767321764000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-10536-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032105356","9783032105363"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-10536-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Selected Areas in Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Toronto, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sacrypt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sacworkshop.org\/SAC25\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}