{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T17:59:35Z","timestamp":1775066375452,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T00:00:00Z","timestamp":1710806400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T00:00:00Z","timestamp":1710806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are cryptographic protocols that offer efficient and privacy-preserving means of verifying NP language relations and have drawn considerable attention for their appealing applications, e.g., verifiable computation and anonymous payment protocol. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity. To tackle this issue, this work seeks to enhance the efficiency and compactness of lattice-based zk-SNARKs, including proof length and common reference string (CRS) length. In this paper, we develop the framework of square span program-based SNARKs and design new zk-SNARKs over cyclotomic rings. Compared with previous works, our construction is without parallel repetition and achieves shorter proof and CRS lengths than previous lattice-based zk-SNARK schemes. Particularly, the proof length of our scheme is around <jats:inline-formula><jats:alternatives><jats:tex-math>$$23.3\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>23.3<\/mml:mn>\n                    <mml:mo>%<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> smaller than the recent shortest lattice-based zk-SNARKs by Ishai et al. (in: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 212\u2013234, 2021), and the CRS length is <jats:inline-formula><jats:alternatives><jats:tex-math>$$3.6\\times$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>3.6<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> smaller. Our constructions follow the framework of Gennaro et al. (in: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 556\u2013573, 2018), and adapt it to the ring setting by slightly modifying the knowledge assumptions. We develop concretely small constructions by using module-switching and key-switching procedures in a novel way.<\/jats:p>","DOI":"10.1186\/s42400-024-00215-x","type":"journal-article","created":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T12:01:52Z","timestamp":1710849712000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Shorter ZK-SNARKs from square span programs over ideal lattices"],"prefix":"10.1186","volume":"7","author":[{"given":"Xi","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-0180-0319","authenticated-orcid":false,"given":"Heyang","family":"Cao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feng-Hao","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhedong","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingsheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,19]]},"reference":[{"issue":"3","key":"215_CR1","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","volume":"9","author":"MR Albrecht","year":"2015","unstructured":"Albrecht MR, Player R, Scott S (2015) On the concrete hardness of learning with errors. J Math Cryptol 9(3):169\u2013203","journal-title":"J Math Cryptol"},{"key":"215_CR2","doi-asserted-by":"crossref","unstructured":"Albrecht MR, Cini V, Lai RW, Malavolta G, Thyagarajan SA (2022) Lattice-based snarks: publicly verifiable, preprocessing, and recursively composable. In: Annual international cryptology conference. Springer, pp 102\u2013132","DOI":"10.1007\/978-3-031-15979-4_4"},{"key":"215_CR3","unstructured":"Alkim E, Ducas L, P\u00f6ppelmann T, Schwabe P (2016) Post-quantum key exchange: a new hope. In: 25th USENIX security symposium (USENIX Security 16), pp 327\u2013343"},{"key":"215_CR4","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF02574039","volume":"13","author":"W Banaszczyk","year":"1995","unstructured":"Banaszczyk W (1995) Inequalities for convex bodies and polar reciprocal lattices in r n. Discrete Comput Geom 13:217\u2013231","journal-title":"Discrete Comput Geom"},{"key":"215_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Sasson E, Chiesa A, Genkin D, Tromer E, Virza M (2013) Snarks for c: verifying program executions succinctly and in zero knowledge. In: Advances in cryptology\u2014CRYPTO 2013: 33rd annual cryptology conference, Santa Barbara, CA, USA, August 18\u201322 2013. Proceedings, Part II. Springer, pp 90\u2013108","DOI":"10.1007\/978-3-642-40084-1_6"},{"key":"215_CR6","unstructured":"Ben-Sasson E, Chiesa A, Tromer E, Virza M (2014) Succinct {Non-Interactive} zero knowledge for a von Neumann architecture. In: 23rd USENIX security symposium (USENIX Security 14), pp 781\u2013796"},{"key":"215_CR7","doi-asserted-by":"crossref","unstructured":"Bitansky N, Canetti R, Chiesa A, Tromer E (2011) From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. Cryptology ePrint Archive","DOI":"10.1145\/2090236.2090263"},{"key":"215_CR8","doi-asserted-by":"crossref","unstructured":"Bitansky N, Canetti R, Chiesa A, Tromer E (2012) From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Proceedings of the 3rd innovations in theoretical computer science conference, pp.326\u2013349","DOI":"10.1145\/2090236.2090263"},{"key":"215_CR9","doi-asserted-by":"crossref","unstructured":"Bitansky N, Chiesa A, Ishai Y, Paneth O, Ostrovsky R (2013) Succinct non-interactive arguments via linear interactive proofs. In: Theory of cryptography: 10th theory of cryptography conference, TCC 2013, Tokyo, Japan, March 3\u20136 2013. Proceedings. Springer, pp 315\u2013333","DOI":"10.1007\/978-3-642-36594-2_18"},{"issue":"4","key":"215_CR10","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1007\/s00145-016-9241-9","volume":"30","author":"N Bitansky","year":"2017","unstructured":"Bitansky N, Canetti R, Chiesa A, Goldwasser S, Lin H, Rubinstein A, Tromer E (2017) The hunting of the snark. J Cryptol 30(4):989\u20131066","journal-title":"J Cryptol"},{"key":"215_CR11","doi-asserted-by":"crossref","unstructured":"Boneh D, Boyen X, Goh EJ (2005) Hierarchical identity based encryption with constant size ciphertext. In: Annual international conference on the theory and applications of cryptographic techniques. Springer, pp 440\u2013456","DOI":"10.1007\/11426639_26"},{"key":"215_CR12","doi-asserted-by":"crossref","unstructured":"Boneh D, Ishai Y, Sahai A, Wu DJ (2017) Lattice-based snargs and their application to more efficient obfuscation. In: annual international conference on the theory and applications of cryptographic techniques. Springer, pp 247\u2013277","DOI":"10.1007\/978-3-319-56617-7_9"},{"key":"215_CR13","unstructured":"Bonneau J, Meckler I, Rao V, Shapiro E (2020) Coda: decentralized cryptocurrency at scale. Cryptology ePrint Archive"},{"issue":"3","key":"215_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2633600","volume":"6","author":"Z Brakerski","year":"2014","unstructured":"Brakerski Z, Gentry C, Vaikuntanathan V (2014) (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans Comput Theory (TOCT) 6(3):1\u201336","journal-title":"ACM Trans Comput Theory (TOCT)"},{"key":"215_CR15","doi-asserted-by":"crossref","unstructured":"Chiesa A, Yogev E (2020) Barriers for succinct arguments in the random oracle model. In: Theory of cryptography: 18th international conference, TCC 2020, Durham, NC, USA, November 16\u201319, 2020, Proceedings, Part II 18. Springer, pp 47\u201376","DOI":"10.1007\/978-3-030-64378-2_3"},{"key":"215_CR16","doi-asserted-by":"crossref","unstructured":"Chung H, Kim D, Kim JH, Kim J (2023) Amortized efficient zk-snark from linear-only rlwe encodings. J Commun Netw","DOI":"10.23919\/JCN.2023.000012"},{"key":"215_CR17","doi-asserted-by":"crossref","unstructured":"Cini V, Lai RW, Malavolta G (2023) Lattice-based succinct arguments from vanishing polynomials. In: Annual international cryptology conference. Springer, pp 72\u2013105","DOI":"10.1007\/978-3-031-38545-2_3"},{"key":"215_CR18","doi-asserted-by":"crossref","unstructured":"Danezis G, Fournet C, Groth J, Kohlweiss M (2014) Square span programs with applications to succinct nizk arguments. In: International conference on the theory and application of cryptology and information security. Springer, pp 532\u2013550","DOI":"10.1007\/978-3-662-45611-8_28"},{"key":"215_CR19","doi-asserted-by":"crossref","unstructured":"Fisch B, Liu Z, Vesely P (2023) Orbweaver: succinct linear functional commitments from lattices. In: Annual international cryptology conference. Springer, pp 106\u2013131","DOI":"10.1007\/978-3-031-38545-2_4"},{"key":"215_CR20","doi-asserted-by":"crossref","unstructured":"Gennaro R, Gentry C, Parno B, Raykova M (2013) Quadratic span programs and succinct nizks without pcps. In: Advances in Cryptology\u2014EUROCRYPT 2013: 32nd annual international conference on the theory and applications of cryptographic techniques, Athens, Greece, May 26\u201330 2013. Proceedings 32. Springer, pp 626\u2013645","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"215_CR21","doi-asserted-by":"crossref","unstructured":"Gennaro R, Minelli M, Nitulescu A, Orr\u00f9 M (2018) Lattice-based zk-snarks from square span programs. In: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 556\u2013573","DOI":"10.1145\/3243734.3243845"},{"key":"215_CR22","doi-asserted-by":"crossref","unstructured":"Gentry C (2009) Fully homomorphic encryption using ideal lattices. In: Proceedings of the forty-first annual ACM symposium on theory of computing, pp 169\u2013178","DOI":"10.1145\/1536414.1536440"},{"key":"215_CR23","doi-asserted-by":"crossref","unstructured":"Gentry C, Wichs D (2011) Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the forty-third annual ACM symposium on theory of computing, pp 99\u2013108","DOI":"10.1145\/1993636.1993651"},{"issue":"1","key":"215_CR24","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser S, Micali S, Rackoff C (1989) The knowledge complexityof interactive proof systems. SIAM J Comput 18(1):186\u2013208","journal-title":"SIAM J Comput"},{"key":"215_CR25","unstructured":"Goldwasser S, Lin H, Rubinstein A (2011) Delegation of computation without rejection problem from designated verifier cs-proofs. Cryptology ePrint Archive"},{"key":"215_CR26","doi-asserted-by":"crossref","unstructured":"Groth J (2010) Short pairing-based non-interactive zero-knowledge arguments. In: Advances in cryptology-ASIACRYPT 2010: 16th international conference on the theory and application of cryptology and information security, Singapore, December 5\u20139 2010. Proceedings 16. Springer, pp 321\u2013340","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"215_CR27","doi-asserted-by":"crossref","unstructured":"Groth J (2016) On the size of pairing-based non-interactive arguments. In: Advances in Cryptology\u2013EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35, pp. 305\u2013326. Springer","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"215_CR28","doi-asserted-by":"crossref","unstructured":"Halevi S, Shoup V (2014) Algorithms in Helib. In: Advances in cryptology\u2014CRYPTO 2014: 34th annual cryptology conference, Santa Barbara, CA, USA, August 17\u201321, 2014, Proceedings, Part I 34. Springer, pp 554\u2013571","DOI":"10.1007\/978-3-662-44371-2_31"},{"key":"215_CR29","unstructured":"Halevi S, Shoup V (2020) Design and implementation of helib: a homomorphic encryption library. Cryptology ePrint Archive"},{"key":"215_CR30","doi-asserted-by":"crossref","unstructured":"Ishai Y, Su H, Wu DJ (2021) Shorter and faster post-quantum designated-verifier zksnarks from lattices. In: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 212\u2013234","DOI":"10.1145\/3460120.3484572"},{"key":"215_CR31","doi-asserted-by":"crossref","unstructured":"Katsumata S, Yamada S (2016) Partitioning via non-linear polynomial functions: more compact ibes from ideal lattices and bilinear maps. In: Advances in cryptology\u2014ASIACRYPT 2016: 22nd international conference on the theory and application of cryptology and information security, Hanoi, Vietnam, December 4\u20138 2016, Proceedings, Part II 22. Springer, pp 682\u2013712","DOI":"10.1007\/978-3-662-53890-6_23"},{"key":"215_CR32","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10623-015-0067-5","volume":"77","author":"T Laarhoven","year":"2015","unstructured":"Laarhoven T, Mosca M, Van De Pol J (2015) Finding shortest lattice vectors faster using quantum search. Des Codes Crypt 77:375\u2013400","journal-title":"Des Codes Crypt"},{"key":"215_CR33","unstructured":"Labs P (2018) Filecoin. https:\/\/filecoin.io\/filecoin.pdf"},{"issue":"3","key":"215_CR34","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","volume":"75","author":"A Langlois","year":"2015","unstructured":"Langlois A, Stehl\u00e9 D (2015) Worst-case to average-case reductions for module lattices. Des Codes Crypt 75(3):565\u2013599","journal-title":"Des Codes Crypt"},{"key":"215_CR35","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V, Peikert C, Regev O (2010) On ideal lattices and learning with errors over rings. In: Advances in cryptology\u2014EUROCRYPT 2010: 29th annual international conference on the theory and applications of cryptographic techniques, French Riviera, May 30\u2013June 3, 2010. Proceedings 29. Springer, pp 1\u201323","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"215_CR36","doi-asserted-by":"crossref","unstructured":"Naganuma K, Yoshino M, Inoue A, Matsuoka Y, Okazaki M, Kunihiro N (2020) Post-quantum zk-snark for arithmetic circuits using qaps. In: 2020 15th Asia joint conference on information security (AsiaJCIS). IEEE, pp 32\u201339","DOI":"10.1109\/AsiaJCIS50894.2020.00017"},{"key":"215_CR37","doi-asserted-by":"crossref","unstructured":"Naor M (2003) On cryptographic assumptions and challenges. In: Annual international cryptology conference. Springer, pp 96\u2013109","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"215_CR38","doi-asserted-by":"crossref","unstructured":"Nitulescu A (2019) Lattice-based zero-knowledge snargs for arithmetic circuits. In: Progress in cryptology\u2014LATINCRYPT 2019: 6th international conference on cryptology and information security in Latin America, Santiago de Chile, Chile, October 2\u20134, 2019, Proceedings 6. Springer, pp 217\u2013236","DOI":"10.1007\/978-3-030-30530-7_11"},{"issue":"2","key":"215_CR39","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/2856449","volume":"59","author":"B Parno","year":"2016","unstructured":"Parno B, Howell J, Gentry C, Raykova M (2016) Pinocchio: nearly practical verifiable computation. Commun ACM 59(2):103\u2013112","journal-title":"Commun ACM"},{"key":"215_CR40","doi-asserted-by":"crossref","unstructured":"Peikert C, Vaikuntanathan V, Waters B (2008) A framework for efficient and composable oblivious transfer. In: Annual international cryptology conference. Springer, pp 554\u2013571","DOI":"10.1007\/978-3-540-85174-5_31"},{"key":"215_CR41","doi-asserted-by":"crossref","unstructured":"Peikert C, Pepin Z, Sharp C (2021) Vector and functional commitments from lattices. In: Theory of cryptography: 19th international conference, TCC 2021, Raleigh, NC, USA, November 8\u201311 2021, Proceedings, Part III 19. Springer, pp 480\u2013511","DOI":"10.1007\/978-3-030-90456-2_16"},{"key":"215_CR42","doi-asserted-by":"crossref","unstructured":"Sasson EB, Chiesa A, Garman C, Green M, Miers I, Tromer E, Virza M (2014) Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE symposium on security and privacy. IEEE, pp 459\u2013474","DOI":"10.1109\/SP.2014.36"},{"key":"215_CR43","doi-asserted-by":"crossref","unstructured":"Wee H, Wu DJ (2023) Succinct vector, polynomial, and functional commitments from lattices. In: Annual international conference on the theory and applications of cryptographic techniques. Springer, pp 385\u2013416","DOI":"10.1007\/978-3-031-30620-4_13"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00215-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-024-00215-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00215-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T12:02:40Z","timestamp":1710849760000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-024-00215-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,19]]},"references-count":43,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["215"],"URL":"https:\/\/doi.org\/10.1186\/s42400-024-00215-x","relation":{},"ISSN":["2523-3246"],"issn-type":[{"value":"2523-3246","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,19]]},"assertion":[{"value":"30 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"33"}}