{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,20]],"date-time":"2026-10-20T02:13:34Z","timestamp":1792462414105,"version":"4.5.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,10,1]],"date-time":"2023-10-01T00:00:00Z","timestamp":1696118400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,10,1]],"date-time":"2023-10-01T00:00:00Z","timestamp":1696118400000},"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":["J Cryptol"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s00145-023-09481-3","type":"journal-article","created":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T19:01:27Z","timestamp":1697223687000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":44,"title":["Rinocchio: SNARKs for Ring Arithmetic"],"prefix":"10.1007","volume":"36","author":[{"given":"Chaya","family":"Ganesh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anca","family":"Nitulescu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4882-0230","authenticated-orcid":false,"given":"Eduardo","family":"Soria-Vazquez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,10,13]]},"reference":[{"key":"9481_CR1","doi-asserted-by":"crossref","unstructured":"M. Abspoel, R. Cramer, I. Damg\u00e5rd, D. Escudero, C. Yuan, Efficient information-theoretic secure multiparty computation over $${\\mathbb{Z}}\/p^k{\\mathbb{Z}}$$ via galois rings. In D. Hofheinz and A. Rosen, editors, TCC\u00a02019, Part\u00a0I, volume 11891 of LNCS, pages 471\u2013501. Springer, Heidelberg (2019)","DOI":"10.1007\/978-3-030-36030-6_19"},{"key":"9481_CR2","series-title":"Part III, volume 10993 of LNCS","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-319-96878-0_22","volume-title":"CRYPTO 2018","author":"S Agrawal","year":"2018","unstructured":"S. Agrawal, C. Ganesh, P. Mohassel, Non-interactive zero-knowledge proofs for composite statements. In H. Shacham and A. Boldyreva, editors, CRYPTO\u00a02018, Part\u00a0III, volume 10993 of LNCS, pages 643\u2013673. Springer, Heidelberg (2018)"},{"key":"9481_CR3","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, D. Genkin, E.Tromer, M. Virza, SNARKs for C: Verifying program executions succinctly and in zero knowledge. In R. Canetti and J.A. Garay, editors, CRYPTO\u00a02013, Part\u00a0II, volume 8043 of LNCS, pages 90\u2013108. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40084-1_6"},{"key":"9481_CR4","unstructured":"E. Ben-Sasson, A. Chiesa, E. Tromer, M. Virza, Succinct non-interactive zero knowledge for a von neumann architecture. In K. Fu and J. Jung, editors, USENIX Security 2014, pages 781\u2013796. USENIX Association (2014)"},{"issue":"2","key":"9481_CR5","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s00145-016-9229-5","volume":"30","author":"F Benhamouda","year":"2017","unstructured":"F. Benhamouda, J. Herranz, M. Joye, B. Libert, Efficient cryptosystems from $$2^k$$-th power residue symbols. J. Cryptol., 30(2), 519\u2013549 (2017)","journal-title":"J. Cryptol."},{"key":"9481_CR6","doi-asserted-by":"crossref","unstructured":"A. Bishnoi, P.L Clark, A. Potukuchi, J.R. Schmitt, On zeros of a polynomial in a finite grid. Combin. Probab. Computi. , 27(3), 310\u2013333 (2018)","DOI":"10.1017\/S0963548317000566"},{"key":"9481_CR7","doi-asserted-by":"crossref","unstructured":"N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, O. Paneth, Succinct non-interactive arguments via linear interactive proofs. In A. Sahai, editor, TCC\u00a02013, volume 7785 of LNCS, pages 315\u2013333. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-36594-2_18"},{"key":"9481_CR8","doi-asserted-by":"crossref","unstructured":"A. Bois, I. Cascudo, D. Fiore, D. Kim, Flexible and efficient verifiable computation on encrypted data. In J. Garay, editor, PKC\u00a02021, Part\u00a0II, volume 12711 of LNCS, pages 528\u2013558. Springer, Heidelberg (2021)","DOI":"10.1007\/978-3-030-75248-4_19"},{"key":"9481_CR9","doi-asserted-by":"crossref","unstructured":"D. Boneh, Y. Ishai, A. Sahai, D.J. Wu, Lattice-based SNARGs and their application to more efficient obfuscation. In J.-S. Coron and J.B. Nielsen, editors, EUROCRYPT\u00a02017, Part\u00a0III, volume 10212 of LNCS, pages 247\u2013277. Springer, Heidelberg (2017)","DOI":"10.1007\/978-3-319-56617-7_9"},{"key":"9481_CR10","doi-asserted-by":"crossref","unstructured":"D. Boneh, Y. Ishai, A. Sahai, D.J. Wu, Quasi-optimal SNARGs via linear multi-prover interactive proofs. In J.B. Nielsen and V. Rijmen, editors, EUROCRYPT\u00a02018, Part\u00a0III, volume 10822 of LNCS, pages 222\u2013255. Springer, Heidelberg (2018)","DOI":"10.1007\/978-3-319-78372-7_8"},{"key":"9481_CR11","doi-asserted-by":"crossref","unstructured":"J. Bootle, A. Cerulli, J. Groth, S.K. Jakobsen, M. Maller, Arya: Nearly linear-time zero-knowledge proofs for correct program execution. In T. Peyrin and S. Galbraith, editors, ASIACRYPT\u00a02018, Part\u00a0I, volume 11272 of LNCS, pages 595\u2013626. Springer, Heidelberg (2018)","DOI":"10.1007\/978-3-030-03326-2_20"},{"key":"9481_CR12","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, Fully homomorphic encryption without modulus switching from classical GapSVP. In R. Safavi-Naini and R. Canetti, editors, CRYPTO\u00a02012, volume 7417 of LNCS, pages 868\u2013886. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-32009-5_50"},{"key":"9481_CR13","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, C. Gentry, V. Vaikuntanathan, (Leveled) fully homomorphic encryption without bootstrapping. In S. Goldwasser, editor, ITCS 2012, pages 309\u2013325. ACM (2012)","DOI":"10.1145\/2090236.2090262"},{"key":"9481_CR14","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, V. Vaikuntanathan, Fully homomorphic encryption from ring-LWE and security for key dependent messages. In P. Rogaway, editor, CRYPTO\u00a02011, volume 6841 of LNCS, pages 505\u2013524. Springer, Heidelberg, (2011)","DOI":"10.1007\/978-3-642-22792-9_29"},{"key":"9481_CR15","doi-asserted-by":"crossref","unstructured":"B. Braun, A.J. Feldman, Z. Ren, S. Setty, A.J. Blumberg, M. Walfish, Verifying computations with state. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 341\u2013357 (2013)","DOI":"10.1145\/2517349.2522733"},{"key":"9481_CR16","doi-asserted-by":"crossref","unstructured":"M. Campanelli, D. Fiore, A. Querol, LegoSNARK: Modular design and composition of succinct zero-knowledge proofs. In L. Cavallaro, J. Kinder, X. Wang, and J. Katz, editors, ACM CCS 2019, pages 2075\u20132092. ACM Press (2019)","DOI":"10.1145\/3319535.3339820"},{"key":"9481_CR17","doi-asserted-by":"crossref","unstructured":"D.G. Cantor, E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras. Acta Inf., 28(7), 693\u2013701 (1991)","DOI":"10.1007\/BF01178683"},{"key":"9481_CR18","unstructured":"D. Catalano, M. \u00a0Di Raimondo, D. Fiore, I. Giacomelli, Monza: Fast maliciously secure two party computation on $${\\mathbb{Z}} _{2}^{k}$$. Cryptology ePrint Archive, Report 2019\/211 (2019) https:\/\/eprint.iacr.org\/2019\/211."},{"key":"9481_CR19","unstructured":"S. Chen, J.H. Cheon, D. Kim, D. Park, Verifiable computing for approximate computation. Cryptology ePrint Archive, Report 2019\/762 (2019) https:\/\/eprint.iacr.org\/2019\/762."},{"key":"9481_CR20","doi-asserted-by":"crossref","unstructured":"A. Chiesa, Y. Hu, M. Maller, P. Mishra, P. Vesely, N.P. Ward, Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In A. Canteaut and Y. Ishai, editors, EUROCRYPT\u00a02020, Part\u00a0I, volume 12105 of LNCS, pages 738\u2013768. Springer, Heidelberg (2020)","DOI":"10.1007\/978-3-030-45721-1_26"},{"key":"9481_CR21","doi-asserted-by":"crossref","unstructured":"I. Chillotti, N. Gama, M. Georgieva, M. Izabach\u00e8ne, TFHE: Fast fully homomorphic encryption over the torus. J. Cryptol., 33(1), 34\u201391 (2020)","DOI":"10.1007\/s00145-019-09319-x"},{"key":"9481_CR22","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, Y. Kalai, S.P. Vadhan, Improved delegation of computation using fully homomorphic encryption. In T. Rabin, editor, CRYPTO\u00a02010, volume 6223 of LNCS, pages 483\u2013501. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-14623-7_26"},{"key":"9481_CR23","doi-asserted-by":"crossref","unstructured":"A. Costache, K. Laine, R. Player, Evaluating the effectiveness of heuristic worst-case noise analysis in FHE. In L. Chen, N. Li, K. Liang, and S.A. Schneider, editors, ESORICS\u00a02020, Part\u00a0II, volume 12309 of LNCS, pages 546\u2013565. Springer, Heidelberg (2020)","DOI":"10.1007\/978-3-030-59013-0_27"},{"key":"9481_CR24","doi-asserted-by":"crossref","unstructured":"C. Costello, C. Fournet, J. Howell, M. Kohlweiss, B. Kreuter, M. Naehrig, B. Parno, S. Zahur, Geppetto: Versatile verifiable computation. In 2015 IEEE Symposium on Security and Privacy, pages 253\u2013270. IEEE (2015)","DOI":"10.1109\/SP.2015.23"},{"key":"9481_CR25","doi-asserted-by":"crossref","unstructured":"A.P.K. Dalskov, E. Lee, E. Soria-Vazquez, Circuit amortization friendly encodingsand their application to statistically secure multiparty computation. In S. Moriai and H. Wang, editors, ASIACRYPT\u00a02020, Part\u00a0III, volume 12493 of LNCS, pages 213\u2013243. Springer, Heidelberg (2020)","DOI":"10.1007\/978-3-030-64840-4_8"},{"key":"9481_CR26","unstructured":"J. Fan, F. Vercauteren, Somewhat practical fully homomorphic encryption. IACR Cryptol. Print Archive, 2012:144 (2012)"},{"key":"9481_CR27","doi-asserted-by":"crossref","unstructured":"D. Fiore, R. Gennaro, V. Pastro, Efficiently verifiable computation on encrypted data. In G.-J. Ahn, M. Yung, and N. Li, editors, ACM CCS 2014, pages 844\u2013855. ACM Press (2014)","DOI":"10.1145\/2660267.2660366"},{"key":"9481_CR28","doi-asserted-by":"crossref","unstructured":"D. Fiore, A. Nitulescu, D. Pointcheval, Boosting verifiable computation on encrypted data. In A. Kiayias, M. Kohlweiss, P. Wallden, and V. Zikas, editors, PKC\u00a02020, Part\u00a0II, volume 12111 of LNCS, pages 124\u2013154. Springer, Heidelberg (2020)","DOI":"10.1007\/978-3-030-45388-6_5"},{"key":"9481_CR29","unstructured":"A. Gabizon, Z.J. Williamson, plookup: A simplified polynomial protocol for lookup tables. Cryptology ePrint Archive, Report 2020\/315 (2020) https:\/\/ia.cr\/2020\/315"},{"key":"9481_CR30","doi-asserted-by":"crossref","unstructured":"R. Gennaro, C. Gentry, B. Parno, Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In T. Rabin, editor, CRYPTO\u00a02010, volume 6223 of LNCS, pages 465\u2013482. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-14623-7_25"},{"key":"9481_CR31","doi-asserted-by":"crossref","unstructured":"R. Gennaro, C. Gentry, B. Parno, M. Raykova, Quadratic span programs and succinct NIZKs without PCPs. In T. Johansson and P.Q. Nguyen, editors, EUROCRYPT\u00a02013, volume 7881 of LNCS, pages 626\u2013645. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"9481_CR32","doi-asserted-by":"crossref","unstructured":"R. Gennaro, M. Minelli, A. Nitulescu, M. Orr\u00f9, Lattice-based zk-SNARKs from square span programs. In D. Lie, M. Mannan, M. Backes, and X. Wang, editors, ACM CCS 2018, pages 556\u2013573. ACM Press (2018)","DOI":"10.1145\/3243734.3243845"},{"key":"9481_CR33","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, Y.T. Kalai, G.N. Rothblum, Delegating computation: interactive proofs for muggles. In R.E. Ladner and C. Dwork, editors, 40th ACM STOC, pages 113\u2013122. ACM Press (2008)","DOI":"10.1145\/1374376.1374396"},{"key":"9481_CR34","doi-asserted-by":"crossref","unstructured":"J. Groth, Short pairing-based non-interactive zero-knowledge arguments. In M. Abe, editor, ASIACRYPT\u00a02010, volume 6477 of LNCS, pages 321\u2013340. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"9481_CR35","doi-asserted-by":"crossref","unstructured":"J. Groth, On the size of pairing-based non-interactive arguments. In M. Fischlin and J.-S. Coron, editors, EUROCRYPT\u00a02016, Part\u00a0II, volume 9666 of LNCS, pages 305\u2013326. Springer, Heidelberg (2016)","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"9481_CR36","doi-asserted-by":"crossref","unstructured":"Y. Ishai, H. Su, D.J. Wu. Shorter and faster post-quantum designated-verifier zkSNARKs from lattices. In G. Vigna and E. Shi, editors, ACM CCS 2021, pages 212\u2013234. ACM Press (2021)","DOI":"10.1145\/3460120.3484572"},{"key":"9481_CR37","unstructured":"A.E. Kosba, D. Papadopoulos, C. Papamanthou, M.F. Sayed, E. Shi, N. Triandopoulos, TRUESET: Faster verifiable set computations. In Kevin Fu and Jaeyeon Jung, editors, USENIX Security 2014, pages 765\u2013780. USENIX Association (2014)"},{"key":"9481_CR38","doi-asserted-by":"crossref","unstructured":"A.E. Kosba, C. Papamanthou, E. Shi, xJsnark: A framework for efficient verifiable computation. In 2018 IEEE Symposium on Security and Privacy, pages 944\u2013961. IEEE Computer Society Press (2018)","DOI":"10.1109\/SP.2018.00018"},{"key":"9481_CR39","doi-asserted-by":"crossref","unstructured":"H. Lipmaa, Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In R. Cramer, editor, TCC\u00a02012, volume 7194 of LNCS, pages 169\u2013189. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"9481_CR40","doi-asserted-by":"crossref","unstructured":"H. Lipmaa, Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. In K. Sako and P. Sarkar, editors, ASIACRYPT\u00a02013, Part\u00a0I, volume 8269 of LNCS, pages 41\u201360. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-42033-7_3"},{"key":"9481_CR41","doi-asserted-by":"crossref","unstructured":"M. Maller, S. Bowe, M. Kohlweiss, S. Meiklejohn, Sonic: Zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In L. Cavallaro, J. Kinder, X. Wang, and J. Katz, editors, ACM CCS 2019, pages 2111\u20132128. ACM Press (2019)","DOI":"10.1145\/3319535.3339817"},{"key":"9481_CR42","doi-asserted-by":"crossref","unstructured":"B. Parno, J. Howell, C. Gentry, M. Raykova, Pinocchio: Nearly practical verifiable computation. In 2013 IEEE Symposium on Security and Privacy, pages 238\u2013252. IEEE Computer Society Press (2013)","DOI":"10.1109\/SP.2013.47"},{"key":"9481_CR43","doi-asserted-by":"crossref","unstructured":"C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In M. Mitzenmacher, editor, 41st ACM STOC, pages 333\u2013342. ACM Press (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"9481_CR44","doi-asserted-by":"crossref","unstructured":"O. Regev, On lattices, learning with errors, random linear codes, and cryptography. In H.N. Gabow and R. Fagin, editors, 37th ACM STOC, pages 84\u201393. ACM Press (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"9481_CR45","doi-asserted-by":"crossref","unstructured":"Z.-X. Wan, Lectures on finite fields and Galois rings. World Scientific Publishing Company (2003)","DOI":"10.1142\/5350"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09481-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09481-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09481-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T16:04:02Z","timestamp":1698163442000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09481-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["9481"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09481-3","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10]]},"assertion":[{"value":"29 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"41"}}