{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T12:48:37Z","timestamp":1770468517273,"version":"3.49.0"},"reference-count":83,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T00:00:00Z","timestamp":1719792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T00:00:00Z","timestamp":1720569600000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Polynomial commitments schemes are a powerful tool that enables one party to commit to a polynomial<jats:italic>p<\/jats:italic>of degree<jats:italic>d<\/jats:italic>, and prove that the committed function evaluates to a certain value<jats:italic>z<\/jats:italic>at a specified point<jats:italic>u<\/jats:italic>, i.e.<jats:inline-formula><jats:alternatives><jats:tex-math>$$p(u) = z$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>p<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>u<\/mml:mi><mml:mo>)<\/mml:mo><mml:mo>=<\/mml:mo><mml:mi>z<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, without revealing any additional information about the polynomial. Recently, polynomial commitments have been extensively used as a cryptographic building block to transform polynomial interactive oracle proofs (PIOPs) into efficient succinct arguments. In this paper, we propose a lattice-based polynomial commitment that achieves succinct proof size and verification time in the degree<jats:italic>d<\/jats:italic>of the polynomial. Extractability of our scheme holds in the random oracle model under a natural ring version of the BASIS assumption introduced by Wee and Wu (EUROCRYPT 2023). Unlike recent constructions of polynomial commitments by Albrecht et al. (CRYPTO 2022), and by Wee and Wu, we do not require any expensive preprocessing steps, which makes our scheme particularly attractive as an ingredient of a PIOP compiler for succinct arguments. We further instantiate our polynomial commitment, together with the PIOP (EUROCRYPT 2020), to obtain a publicly-verifiable trusted-setup succinct argument for Rank-1 Constraint System (R1CS). Performance-wise, we achieve<jats:inline-formula><jats:alternatives><jats:tex-math>$$17$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>17<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>MB proof size for<jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{20}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mn>2<\/mml:mn><mml:mn>20<\/mml:mn><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>constraints, which is<jats:inline-formula><jats:alternatives><jats:tex-math>$$15$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>15<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>X smaller than currently the only publicly-verifiable lattice-based SNARK proposed by Albrecht et al.<\/jats:p>","DOI":"10.1007\/s00145-024-09511-8","type":"journal-article","created":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T00:06:16Z","timestamp":1720569976000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3702-1780","authenticated-orcid":false,"given":"Giacomo","family":"Fenzi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0000-3377-0632","authenticated-orcid":false,"given":"Hossein","family":"Moghaddas","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8240-6167","authenticated-orcid":false,"given":"Ngoc Khanh","family":"Nguyen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,10]]},"reference":[{"key":"9511_CR1","doi-asserted-by":"crossref","unstructured":"S. Agrawal, E. Kirshanova, D. Stehl\u00e9, A. Yadav, Practical, round-optimal lattice-based blind signatures, in CCS (ACM, 2022), pp. 39\u201353","DOI":"10.1145\/3548606.3560650"},{"key":"9511_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, Generating hard instances of lattice problems. in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. STOC \u201996 (1996), pp. 99\u2013108","DOI":"10.1145\/237814.237838"},{"key":"9511_CR3","doi-asserted-by":"crossref","unstructured":"M.R. Albrecht, V. Cini, R.W.F. Lai, G. Malavolta, S.A.K. Thyagarajan, Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable\u2014(Extended Abstract), in CRYPTO (2). Lecture Notes in Computer Science, Vol. 13508 (Springer, 2022), pp. 102\u2013132","DOI":"10.1007\/978-3-031-15979-4_4"},{"key":"9511_CR4","unstructured":"M.R. Albrecht, G. Fenzi, O. Lapiha, N.K. Nguyen, SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions. Cryptology ePrint Archive, Paper 2023\/1469. 2023. URL: https:\/\/eprint.iacr.org\/2023\/1469"},{"key":"9511_CR5","doi-asserted-by":"crossref","unstructured":"M.R. Albrecht, R.W.F. Lai, Subtractive Sets over Cyclotomic Rings\u2014Limits of Schnorr-Like Arguments over Lattices, in CRYPTO (2). Lecture Notes in Computer Science, Vol. 12826 (Springer, 2021), pp. 519\u2013548.","DOI":"10.1007\/978-3-030-84245-1_18"},{"key":"9511_CR6","unstructured":"E. Alkim, L. Ducas, T. P\u00f6ppelmann, P. Schwabe, Post-quantum Key Exchange\u2014A New Hope, in USENIX Security Symposium, (USENIX Association, 2016), pp. 327\u2013343"},{"key":"9511_CR7","unstructured":"T. Attema, Compressed Sigma-protocol theory. PhD Thesis (2023). URL: https:\/\/scholarlypublications.universiteitleiden.nl\/access\/item%3A3619598\/view"},{"key":"9511_CR8","doi-asserted-by":"crossref","unstructured":"T. Attema, R. Cramer, L. Kohl, A compressed $$\\Sigma $$-protocol theory for lattices, in CRYPTO (2). Lecture Notes in Computer Science, vol. 12826 (Springer, 2021), pp. 549\u2013579","DOI":"10.1007\/978-3-030-84245-1_19"},{"key":"9511_CR9","doi-asserted-by":"crossref","unstructured":"T. Attema, S. Fehr, Parallel repetition of $$(k_1,\\dots ,k_{\\mu })$$-special-sound multi-round interactive proofs, in CRYPTO (1). Lecture Notes in Computer Science, vol. 13507 (Springer, 2022), pp. 415\u2013443","DOI":"10.1007\/978-3-031-15802-5_15"},{"issue":"4","key":"9511_CR10","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/s00145-023-09478-y","volume":"36","author":"T Attema","year":"2023","unstructured":"T. Attema, S. Fehr, M. Kloo\u00df, Fiat-Shamir Transformation of Multi-Round Interactive Proofs (Extended Version). J. Cryptol. 36(4), 36 (2023)","journal-title":"J. Cryptol."},{"key":"9511_CR11","unstructured":"T. Attema, S. Fehr, N. Resch, A generalized special-soundness notion and its knowledge extractors. Cryptology ePrint Archive, Paper 2023\/818. 2023. URL: https:\/\/eprint.iacr.org\/2023\/818"},{"key":"9511_CR12","doi-asserted-by":"crossref","unstructured":"T. Attema, V. Lyubashevsky, G. Seiler, Practical product proofs for lattice commitments, in CRYPTO (2). Lecture Notes in Computer Science, vol. 12171 (Springer, 2020), pp. 470\u2013499","DOI":"10.1007\/978-3-030-56880-1_17"},{"key":"9511_CR13","unstructured":"D. Balb\u00e1s, D. Catalano, D. Fiore, R.W.F. Lai, Functional commitments for circuits from falsifiable assumptions. Cryptology ePrint Archive, Paper 2022\/1365 (2022). URL: https:\/\/eprint.iacr.org\/2022\/1365"},{"key":"9511_CR14","doi-asserted-by":"crossref","unstructured":"C. Baum, J. Bootle, A. Cerulli, R. del Pino, J. Groth, V. Lyubashevsky, Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits, in CRYPTO (2018), pp. 669\u2013699","DOI":"10.1007\/978-3-319-96881-0_23"},{"key":"9511_CR15","doi-asserted-by":"crossref","unstructured":"C. Baum, I. Damg\u00e5rd, V. Lyubashevsky, S. Oechsner, C. Peikert, More efficient commitments from structured lattice assumptions, in SCN (2018), pp. 368\u2013385","DOI":"10.1007\/978-3-319-98113-0_20"},{"key":"9511_CR16","doi-asserted-by":"crossref","unstructured":"A. Becker, L. Ducas, N. Gama, T. Laarhoven, New directions in nearest neighbor searching with applications to lattice sieving, in SODA (SIAM, 2016), pp. 10\u201324","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"9511_CR17","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, Scalable zero knowledge with no trusted setup, in Proceedings of the 39th Annual International Cryptology Conference (CRYPTO \u201919, 2019), pp. 733\u2013764","DOI":"10.1007\/978-3-030-26954-8_23"},{"key":"9511_CR18","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, N. Spooner, Interactive oracle proofs. in Proceedings of the 14th Theory of Cryptography Conference (TCC \u201916-B, 2016), pp. 31\u201360","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"9511_CR19","doi-asserted-by":"crossref","unstructured":"F. Benhamouda, J. Camenisch, S. Krenn, V. Lyubashevsky, G. Neven, Better zero-knowledge proofs for lattice encryption and their application to group signatures, in ASIACRYPT (2014), pp. 551\u2013572","DOI":"10.1007\/978-3-662-45611-8_29"},{"key":"9511_CR20","doi-asserted-by":"crossref","unstructured":"W. Beullens, G. Seiler, LaBRADOR: compact proofs for R1CS from Module-SIS, in CRYPTO (5). Lecture Notes in Computer Science, vol. 14085 (Springer, 2023), pp. 518\u2013548","DOI":"10.1007\/978-3-031-38554-4_17"},{"key":"9511_CR21","doi-asserted-by":"crossref","unstructured":"N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, O. Paneth, Succinct non-interactive arguments via linear interactive proofs, in Proceedings of the 10th Theory of Cryptography Conference. TCC \u201913 (2013), pp. 315\u2013333","DOI":"10.1007\/978-3-642-36594-2_18"},{"key":"9511_CR22","doi-asserted-by":"crossref","unstructured":"J. Bootle, A. Cerulli, P. Chaidos, J. Groth, C. Petit, Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting, in EUROCRYPT (2016), pp. 327\u2013357","DOI":"10.1007\/978-3-662-49896-5_12"},{"key":"9511_CR23","doi-asserted-by":"crossref","unstructured":"J. Bootle, A. Chiesa, Y. Hu, M. Orr\u00f9, Gemini: elastic SNARKs for diverse environments, in Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT \u201922, 2022), pp. 427\u2013457","DOI":"10.1007\/978-3-031-07085-3_15"},{"key":"9511_CR24","doi-asserted-by":"crossref","unstructured":"J. Bootle, A. Chiesa, K. Sotiraki, Sumcheck arguments and their applications. in CRYPTO (1). Lecture Notes in Computer Science, vol. 12825 (Springer, 2021), pp. 742\u2013773","DOI":"10.1007\/978-3-030-84242-0_26"},{"key":"9511_CR25","doi-asserted-by":"publisher","unstructured":"J. Bootle, A. Chiesa, K. Sotiraki, Lattice-based succinct arguments for NP with polylogarithmic-time verification, in Advances in Cryptology - CRYPTO 2023. Ed. by Helena Handschuh and Anna Lysyanskaya. Lecture Notes in Computer Science, vol. 14082. Full version available at https:\/\/eprint.iacr.org\/2023\/930.pdf (Springer, 2023), pp. 227\u2013251. https:\/\/doi.org\/10.1007\/978-3-031-38545-2_8","DOI":"10.1007\/978-3-031-38545-2_8"},{"key":"9511_CR26","doi-asserted-by":"crossref","unstructured":"J. Bootle, V. Lyubashevsky, N.K. Nguyen, G. Seiler, A non-PCP approach to succinct quantum-safe zero-knowledge, in CRYPTO (2). Lecture Notes in Computer Science, vol. 12171 (Springer, 2020), pp. 441\u2013469","DOI":"10.1007\/978-3-030-56880-1_16"},{"key":"9511_CR27","doi-asserted-by":"crossref","unstructured":"J. Bootle, V. Lyubashevsky, N.K. Nguyen, A. Sorniotti, A Framework for Practical Anonymous Credentials from Lattices. To appear at CRYPTO (2023). 2023. URL: https:\/\/eprint.iacr.org\/2023\/560","DOI":"10.1007\/978-3-031-38545-2_13"},{"key":"9511_CR28","doi-asserted-by":"crossref","unstructured":"J.W. Bos et al. CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM, in 2018 IEEE European Symposium on Security and Privacy, EuroS &P (2018), pp. 353\u2013367","DOI":"10.1109\/EuroSP.2018.00032"},{"key":"9511_CR29","doi-asserted-by":"crossref","unstructured":"C. Boschini, A. Takahashi, M. Tibouchi, MuSig-L: lattice-based multi-signature with single-round online phase. (2022). URL: https:\/\/eprint.iacr.org\/2022\/1036","DOI":"10.1007\/978-3-031-15979-4_10"},{"key":"9511_CR30","doi-asserted-by":"crossref","unstructured":"B. B\u00fcnz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, G. Maxwell, Bulletproofs: short proofs for confidential transactions and more, in IEEE Symposium on Security and Privacy (2018), pp. 315\u2013334","DOI":"10.1109\/SP.2018.00020"},{"key":"9511_CR31","doi-asserted-by":"crossref","unstructured":"B. B\u00fcnz, B. Fisch, A. Szepieniec, Transparent SNARKs from DARK compilers, in EUROCRYPT (1). Lecture Notes in Computer Science, vol. 12105 (Springer, 2020), pp. 677\u2013706","DOI":"10.1007\/978-3-030-45721-1_24"},{"key":"9511_CR32","unstructured":"B. B\u00fcnz, B. Fisch, Multilinear Schwartz-Zippel mod N with Applications to Succinct Arguments. Cryptology ePrint Archive, Paper 2022\/458. 2022. URL: https:\/\/eprint.iacr.org\/2022\/458"},{"key":"9511_CR33","doi-asserted-by":"crossref","unstructured":"R. Canetti, Y. Chen, J. Holmgren, A. Lombardi, G.N. Rothblum, R.D. Rothblum, D. Wichs, Fiat-Shamir: from practice to theory, STOC (ACM, 2019), pp. 1082\u20131090","DOI":"10.1145\/3313276.3316380"},{"issue":"4","key":"9511_CR34","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1008731.1008734","volume":"51","author":"R Canetti","year":"2004","unstructured":"R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology, revisited. J. ACM 51(4), 557\u2013594 (2004)","journal-title":"J. ACM"},{"key":"9511_CR35","unstructured":"L. de Castro, C. Peikert, Functional Commitments for all functions, with transparent setup, in IACR Cryptol. ePrint Arch (2022), p. 1368"},{"key":"9511_CR36","doi-asserted-by":"crossref","unstructured":"Y. Chen, P.Q. Nguyen, BKZ 2.0: better lattice security estimates, in ASIACRYPT. Lecture Notes in Computer Science, vol. 7073 (Springer, 2011), pp. 1\u201320","DOI":"10.1007\/978-3-642-25385-0_1"},{"key":"9511_CR37","doi-asserted-by":"crossref","unstructured":"A. Chiesa, Y. Hu, M. Maller, P. Mishra, N. Vesely, N. Ward, Marlin: preprocessing zkSNARKs with universal and updatable SRS, in Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT \u201920 (2020), pp. 738\u2013768","DOI":"10.1007\/978-3-030-45721-1_26"},{"key":"9511_CR38","doi-asserted-by":"crossref","unstructured":"A.R. Choudhuri, A. Jain, Z. Jin, SNARGs for $$\\cal{P}$$ from LWE, in FOCS (IEEE, 2021), pp. 68\u201379","DOI":"10.1109\/FOCS52979.2021.00016"},{"key":"9511_CR39","doi-asserted-by":"crossref","unstructured":"V. Cini, R.W.F. Lai, G. Malavolta, Lattice-based succinct arguments from vanishing polynomials, in Advances in Cryptology \u2013 CRYPTO 2023. Ed. by Helena Handschuh and Anna Lysyanskaya (Springer Nature Switzerland, Cham, 2023), pp. 72\u2013105","DOI":"10.1007\/978-3-031-38545-2_3"},{"key":"9511_CR40","doi-asserted-by":"crossref","unstructured":"L. Devadas, R. Goyal, Y. Kalai, V. Vaikuntanathan, Rate-1 non-interactive arguments for batch-NP and applications, in FOCS (IEEE, 2022), pp. 1057\u20131068","DOI":"10.1109\/FOCS54457.2022.00103"},{"key":"9511_CR41","doi-asserted-by":"crossref","unstructured":"J. Don, S. Fehr, C. Majenz, The measure-and-reprogram technique 2.0: multi-round Fiat-Shamir and more, in CRYPTO (3). Lecture Notes in Computer Science, vol. 12172 (Springer, 2020), pp. 602\u2013631","DOI":"10.1007\/978-3-030-56877-1_21"},{"issue":"1","key":"9511_CR42","doi-asserted-by":"publisher","first-page":"238","DOI":"10.46586\/tches.v2018.i1.238-268","volume":"2018","author":"L Ducas","year":"2018","unstructured":"L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, D. Stehl\u00e9, CRYSTALS-Dilithium: a lattice-based digital signature scheme, in IACR Trans. Cryptogr. Hardw. Embed. Syst., vol. 2018(1), pp. 238\u2013268 (2018)","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"9511_CR43","doi-asserted-by":"crossref","unstructured":"L. Ducas, V. Lyubashevsky, T. Prest, Efficient identity-based encryption over NTRU lattices, in ASIACRYPT (2014), pp. 22\u201341","DOI":"10.1007\/978-3-662-45608-8_2"},{"key":"9511_CR44","doi-asserted-by":"crossref","unstructured":"M.F. Esgin, N.K. Nguyen, G. Seiler, Practical Exact proofs from lattices: new techniques to exploit fully-splitting rings, in ASIACRYPT (2) (2020), pp. 259\u2013288","DOI":"10.1007\/978-3-030-64834-3_9"},{"key":"9511_CR45","doi-asserted-by":"crossref","unstructured":"M.F. Esgin, R.K. Zhao, R. Steinfeld, J.K. Liu, D. Liu, MatRiCT: efficient, scalable and post-quantum blockchain confidential transactions protocol, in CCS (ACM, 2019), pp. 567\u2013584","DOI":"10.1145\/3319535.3354200"},{"key":"9511_CR46","doi-asserted-by":"crossref","unstructured":"A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems, in CRYPTO (1986), pp. 186\u2013194","DOI":"10.1007\/3-540-47721-7_12"},{"key":"9511_CR47","doi-asserted-by":"crossref","unstructured":"B. Fisch, Z. Liu, P. Vesely, Orbweaver: succinct linear functional commitments from lattices, in Advances in Cryptology \u2013 CRYPTO 2023. Ed. by Helena Handschuh and Anna Lysyanskaya (Springer Nature Switzerland, Cham, 2023), pp. 106\u2013131","DOI":"10.1007\/978-3-031-38545-2_4"},{"key":"9511_CR48","unstructured":"P.-A. Fouque et al. Falcon: Fast-Fourier lattice-based compact signatures over NTRU. Tech. rep. https:\/\/falcon-sign.info\/falcon.pdf (2020)"},{"key":"9511_CR49","doi-asserted-by":"crossref","unstructured":"R. Gennaro, M. Minelli, A. Nitulescu, M. Orr\u00f9, Lattice-based zk-SNARKs from square span programs. in Proceedings of the 25th ACM Conference on Computer and Communications Security. CCS \u201918 (2018), pp. 556\u2013573","DOI":"10.1145\/3243734.3243845"},{"key":"9511_CR50","doi-asserted-by":"crossref","unstructured":"C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in STOC (2008), pp. 197\u2013206","DOI":"10.1145\/1374376.1374407"},{"key":"9511_CR51","unstructured":"A. Golovnev, J. Lee, S.T.V. Setty, J. Thaler, R.S. Wahby, Brakedown: linear-time and post-quantum SNARKs for R1CS, in IACR Cryptol. ePrint Arch. (2021), p. 1043"},{"key":"9511_CR52","doi-asserted-by":"crossref","unstructured":"J. Hoffstein, N. Howgrave-Graham, J. Pipher, J.H. Silverman, W. Whyte, NTRUSIGN: digital signatures using the NTRU lattice, in CT-RSA (2003), pp. 122\u2013140","DOI":"10.1007\/3-540-36563-X_9"},{"key":"9511_CR53","doi-asserted-by":"crossref","unstructured":"J. Holmgren, A. Lombardi, R.D. Rothblum, Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge), in STOC (ACM, 2021), pp. 750\u2013760","DOI":"10.1145\/3406325.3451116"},{"key":"9511_CR54","doi-asserted-by":"crossref","unstructured":"J. Hulett, R. Jawale, D. Khurana, A. Srinivasan, SNARGs for P from Sub-exponential DDH and QR, in EUROCRYPT (2). Lecture Notes in Computer Sciencem, vol. 13276 (Springer, 2022), pp. 520\u2013549","DOI":"10.1007\/978-3-031-07085-3_18"},{"key":"9511_CR55","doi-asserted-by":"crossref","unstructured":"Y. Ishai, H. Su, D. J. Wu, Shorter and faster post-quantum designated-verifier zkSNARKs from lattices, in CCS (ACM, 2021), pp. 212\u2013234","DOI":"10.1145\/3460120.3484572"},{"key":"9511_CR56","unstructured":"C. Jeudy, A. Roux-Langlois, O. Sanders, Lattice Signature with Efficient Protocols, Application to Anonymous Credentials. Cryptology ePrint Archive, Paper 2022\/509. (2022). URL: https:\/\/eprint.iacr.org\/2022\/509"},{"key":"9511_CR57","doi-asserted-by":"crossref","unstructured":"Y. Kalai, A. Lombardi, V. Vaikuntanathan, D. Wichs, Boosting batch arguments and RAM delegation, in STOC (ACM, 2023), pp. 1545\u20131552","DOI":"10.1145\/3564246.3585200"},{"key":"9511_CR58","doi-asserted-by":"crossref","unstructured":"A. Kate, G.M. Zaverucha, I. Goldberg, Constant-size commitments to polynomials and their applications, in ASIACRYPT. Lecture Notes in Computer Science, vol. 6477 (Springer, 2010), pp. 177\u2013194","DOI":"10.1007\/978-3-642-17373-8_11"},{"key":"9511_CR59","doi-asserted-by":"crossref","unstructured":"S. Katsumata. A new simple technique to bootstrap various lattice zero-knowledge proofs to QROM secure NIZKs, in CRYPTO (2). Lecture Notes in Computer Science, vol. 12826 (Springer, 2021), pp. 580\u2013610","DOI":"10.1007\/978-3-030-84245-1_20"},{"key":"9511_CR60","doi-asserted-by":"crossref","unstructured":"R.W.F. Lai, G. Malavolta, N. Spooner, Quantum rewinding for many-round protocols, in TCC (1). Lecture Notes in Computer Science, vol. 13747 (Springer, 2022), pp. 80\u2013109","DOI":"10.1007\/978-3-031-22318-1_4"},{"issue":"3","key":"9511_CR61","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","volume":"75","author":"A Langlois","year":"2015","unstructured":"A. Langlois, D. Stehl\u00e9, Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75(3), 565\u2013599 (2015)","journal-title":"Des. Codes Cryptogr."},{"key":"9511_CR62","doi-asserted-by":"crossref","unstructured":"J. Lee, Dory: efficient, transparent arguments for generalised inner products and polynomial commitments, in TCC (2). Lecture Notes in Computer Science, vol. 13043 (Springer, 2021), pp. 1\u201334","DOI":"10.1007\/978-3-030-90453-1_1"},{"key":"9511_CR63","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/BF01457454","volume":"261","author":"A Lenstra","year":"1982","unstructured":"A. Lenstra, H. Lenstra Jr., L. Lovasz, Factoring polynomials with rational coefficients. Mathematische Annalen 261, 513\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"key":"9511_CR64","unstructured":"B. Libert, S.C. Ramanna, M. Yung, Functional commitment schemes: from polynomial commitments to pairing-based accumulators from simple assumptions, in ICALP. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, vol. 55 (2016), pp. 30:1\u201330:14"},{"key":"9511_CR65","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, Fiat-Shamir with Aborts: applications to lattice and factoring-based signatures, in ASIACRYPT. (2009), pp. 598\u2013616","DOI":"10.1007\/978-3-642-10366-7_35"},{"key":"9511_CR66","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, Lattice signatures without trapdoors, in EUROCRYPT. (2012), pp. 738\u2013755","DOI":"10.1007\/978-3-642-29011-4_43"},{"key":"9511_CR67","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, N.K. Nguyen, BLOOM: bimodal lattice one-out-of-many proofs and applications, in ASIACRYPT (4). Lecture Notes in Computer Science, vol. 13794 (Springer, 2022), pp. 95\u2013125","DOI":"10.1007\/978-3-031-22972-5_4"},{"key":"9511_CR68","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, N.K. Nguyen, M. Plan\u00e7on, Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general, in CRYPTO (2). Lecture Notes in Computer Science, vol. 13508 (Springer, 2022), pp. 71\u2013101","DOI":"10.1007\/978-3-031-15979-4_3"},{"key":"9511_CR69","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, C. Peikert, O. Regev, A toolkit for ring-LWE cryptography, in EUROCRYPT. (2013), pp. 35\u201354","DOI":"10.1007\/978-3-642-38348-9_3"},{"key":"9511_CR70","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, G. Seiler, Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs, in EUROCRYPT (1) (Springer, 2018), pp. 204\u2013224","DOI":"10.1007\/978-3-319-78381-9_8"},{"issue":"3","key":"9511_CR71","doi-asserted-by":"publisher","first-page":"180","DOI":"10.46586\/tches.v2019.i3.180-201","volume":"2019","author":"V Lyubashevsky","year":"2019","unstructured":"V. Lyubashevsky, G. Seiler, NTTRU: truly fast NTRU using NTT, in IACR Trans. Cryptogr. Hardw. Embed. Syst. vol. 2019(3) (2019), pp. 180\u2013201","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"9511_CR72","doi-asserted-by":"crossref","unstructured":"D. Micciancio, C. Peikert, Trapdoors for lattices: simpler, tighter, faster, smaller, in EUROCRYPT. (2012), pp. 700\u2013718","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"9511_CR73","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D Micciancio","year":"2007","unstructured":"D. Micciancio, O. Regev, Worst-case to average-case reductions based on Gaussian measures, in SIAM Journal on Computing 37, 267\u2013302 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"9511_CR74","doi-asserted-by":"publisher","unstructured":"D. Micciancio, O. Regev, Lattice-based Cryptography, in Post-Quantum Cryptography. Ed. by Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen. Berlin, Heidelberg: Springer Berlin Heidelberg, (2009), pp. 147\u2013191. ISBN: 978-3-540-88702-7. https:\/\/doi.org\/10.1007\/978-3-540-88702-7_5","DOI":"10.1007\/978-3-540-88702-7_5"},{"key":"9511_CR75","doi-asserted-by":"crossref","unstructured":"N.K. Nguyen, G. Seiler, Practical sublinear proofs for R1CS from lattices, in CRYPTO (2). Lecture Notes in Computer Science. vol. 13508 (Springer, 2022), pp. 133\u2013162","DOI":"10.1007\/978-3-031-15979-4_5"},{"key":"9511_CR76","doi-asserted-by":"crossref","unstructured":"C. Peikert, Z. Pepin, C. Sharp, Vector and functional commitments from lattices, in TCC (3). Lecture Notes in Computer Science, vol. 13044 (Springer, 2021), pp. 480\u2013511","DOI":"10.1007\/978-3-030-90456-2_16"},{"key":"9511_CR77","doi-asserted-by":"crossref","unstructured":"C.-P. Schnorr, M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181\u2013199 (1994)","DOI":"10.1007\/BF01581144"},{"key":"9511_CR78","unstructured":"G. Seiler, Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography, in IACR Cryptology ePrint Archive 2018 (2018). http:\/\/eprint.iacr.org\/2018\/039, p. 39"},{"key":"9511_CR79","doi-asserted-by":"crossref","unstructured":"S. Setty, Spartan: efficient and general-purpose zkSNARKs without trusted setup, inProceedings of the 40th Annual International Cryptology Conference. CRYPTO \u201920. Referencing Cryptology ePrint Archive, Report 2019\/550, revision from 2020.02.28. (2020), pp. 704\u2013737","DOI":"10.1007\/978-3-030-56877-1_25"},{"key":"9511_CR80","unstructured":"D. Stehl\u00e9, R. Steinfeld, Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices, in IACR Cryptol. ePrint Arch. (2013), p. 4"},{"key":"9511_CR81","unstructured":"R. Steinfeld, A. Sakzad, M.F. Esgin, V. Kuchta, Private Re-Randomization for Module LWE and Applications to Quasi-Optimal ZK-SNARKs. Cryptology ePrint Archive, Paper 2022\/1690. (2022). URL: https:\/\/eprint.iacr.org\/2022\/1690"},{"key":"9511_CR82","doi-asserted-by":"crossref","unstructured":"H. Wee, D.J. Wu, Lattice-based functional commitments: fast verification and cryptanalysis, in Advances in Cryptology \u2013 ASIACRYPT 2023. Ed. by Jian Guo and Ron Steinfeld. (Springer Nature, Singapore, 2023), pp. 201\u2013235. ISBN: 978-981-99-8733-7","DOI":"10.1007\/978-981-99-8733-7_7"},{"key":"9511_CR83","doi-asserted-by":"crossref","unstructured":"H. Wee, D.J. Wu, Succinct vector, polynomial, and functional commitments from lattices, EUROCRYPT (3). Lecture Notes in Computer Science, vol. 14006. Full version: https:\/\/eprint.iacr.org\/2022\/1515. (Springer, 2023), pp. 385\u2013416","DOI":"10.1007\/978-3-031-30620-4_13"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09511-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-024-09511-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09511-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,23]],"date-time":"2024-11-23T19:21:50Z","timestamp":1732389710000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-024-09511-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":83,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["9511"],"URL":"https:\/\/doi.org\/10.1007\/s00145-024-09511-8","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"27 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"31"}}