{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T17:30:59Z","timestamp":1783791059209,"version":"3.55.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T00:00:00Z","timestamp":1483488000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00145-016-9249-1","type":"journal-article","created":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T16:27:39Z","timestamp":1483547259000},"page":"23-59","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Practical Homomorphic Message Authenticators for Arithmetic Circuits"],"prefix":"10.1007","volume":"31","author":[{"given":"Dario","family":"Catalano","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dario","family":"Fiore","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,1,4]]},"reference":[{"key":"9249_CR1","doi-asserted-by":"crossref","unstructured":"S.\u00a0Agrawal and D.\u00a0Boneh. Homomorphic MACs: MAC-based integrity for network coding, in M.\u00a0Abdalla, D.\u00a0Pointcheval, P.-A. Fouque, and D.\u00a0Vergnaud, editors, ACNS 09, volume 5536 of LNCS (Springer, 2009), pp. 292\u2013305","DOI":"10.1007\/978-3-642-01957-9_18"},{"key":"9249_CR2","doi-asserted-by":"crossref","unstructured":"J.\u00a0H. Ahn, D.\u00a0Boneh, J.\u00a0Camenisch, S.\u00a0Hohenberger, a.\u00a0shelat, and B.\u00a0Waters. Computing on authenticated data, in R.\u00a0Cramer, editor, TCC\u00a02012, volume 7194 of LNCS (Springer, 2012), pp. 1\u201320","DOI":"10.1007\/978-3-642-28914-9_1"},{"key":"9249_CR3","doi-asserted-by":"crossref","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, and E.\u00a0Kushilevitz. From secrecy to soundness: Efficient verification via secure computation, in S.\u00a0Abramsky, C.\u00a0Gavoille, C.\u00a0Kirchner, F.\u00a0Meyer auf der Heide, and P.G. Spirakis, editors, ICALP 2010, Part I, volume 6198 of LNCS (Springer, 2010), pp. 152\u2013163","DOI":"10.1007\/978-3-642-14165-2_14"},{"key":"9249_CR4","doi-asserted-by":"crossref","unstructured":"N.\u00a0Attrapadung and B.\u00a0Libert. Homomorphic network coding signatures in the standard model, in D.\u00a0Catalano, N.\u00a0Fazio, R.\u00a0Gennaro, and A.\u00a0Nicolosi, editors, PKC\u00a02011, volume 6571 of LNCS (Springer, 2011), pp. 17\u201334","DOI":"10.1007\/978-3-642-19379-8_2"},{"key":"9249_CR5","doi-asserted-by":"crossref","unstructured":"N.\u00a0Attrapadung, B.\u00a0Libert, and T.\u00a0Peters. Computing on authenticated data: New privacy definitions and constructions, in X.\u00a0Wang and K.\u00a0Sako, editors, ASIACRYPT\u00a02012, volume 7658 of LNCS (Springer, 2012), pp. 367\u2013385","DOI":"10.1007\/978-3-642-34961-4_23"},{"key":"9249_CR6","doi-asserted-by":"crossref","unstructured":"N.\u00a0Attrapadung, B.\u00a0Libert, and T.\u00a0Peters. Efficient completely context-hiding quotable and linearly homomorphic signatures, in K.\u00a0Kurosawa and G.\u00a0Hanaoka, editors, PKC\u00a02013, volume 7778 of LNCS (Springer, 2013), pp. 386\u2013404","DOI":"10.1007\/978-3-642-36362-7_24"},{"key":"9249_CR7","doi-asserted-by":"crossref","unstructured":"M.\u00a0Backes, D.\u00a0Fiore, and R.\u00a0M. Reischuk. Verifiable delegation of computation on outsourced data, in A.-R. Sadeghi, V.\u00a0D. Gligor, and M.\u00a0Yung, editors, ACM CCS 13 (ACM Press, 2013) pp. 863\u2013874","DOI":"10.1145\/2508859.2516681"},{"key":"9249_CR8","doi-asserted-by":"crossref","unstructured":"S.\u00a0Benabbas, R.\u00a0Gennaro, and Y.\u00a0Vahlis. Verifiable delegation of computation over large datasets, in P.\u00a0Rogaway, editor, CRYPTO\u00a02011, volume 6841 of LNCS (Springer, 2011), pp. 111\u2013131","DOI":"10.1007\/978-3-642-22792-9_7"},{"key":"9249_CR9","doi-asserted-by":"crossref","unstructured":"N.\u00a0Bitansky, R.\u00a0Canetti, A.\u00a0Chiesa, and E.\u00a0Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again, in S.\u00a0Goldwasser, editor, ITCS 2012 (ACM 2012), pp. 326\u2013349","DOI":"10.1145\/2090236.2090263"},{"key":"9249_CR10","doi-asserted-by":"crossref","unstructured":"N.\u00a0Bitansky, R.\u00a0Canetti, A.\u00a0Chiesa, and E.\u00a0Tromer. Recursive composition and bootstrapping for SNARKs and proof-carrying data. Cryptology ePrint Archive, Report 2012\/095, 2012. https:\/\/2.zoppoz.workers.dev:443\/http\/eprint.iacr.org\/2012\/095","DOI":"10.1145\/2488608.2488623"},{"key":"9249_CR11","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, D.\u00a0Freeman, J.\u00a0Katz, and B.\u00a0Waters. Signing a linear subspace: Signature schemes for network coding, in S.\u00a0Jarecki and G.\u00a0Tsudik, editors, PKC\u00a02009, volume 5443 of LNCS (Springer, 2009), pp. 68\u201387","DOI":"10.1007\/978-3-642-00468-1_5"},{"key":"9249_CR12","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh and D.\u00a0M. Freeman. Homomorphic signatures for polynomial functions, in K.\u00a0G. Paterson, editor, EUROCRYPT\u00a02011, volume 6632 of LNCS (Springer, 2011), pp. 149\u2013168","DOI":"10.1007\/978-3-642-20465-4_10"},{"key":"9249_CR13","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh and D.\u00a0M. Freeman. Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures, in D.\u00a0Catalano, N.\u00a0Fazio, R.\u00a0Gennaro, and A.\u00a0Nicolosi, editors, PKC\u00a02011, volume 6571 of LNCS (Springer, 2011), pp. 1\u201316","DOI":"10.1007\/978-3-642-19379-8_1"},{"key":"9249_CR14","doi-asserted-by":"crossref","unstructured":"X.\u00a0Boyen. The uber-assumption family (invited talk), in S.D. Galbraith and K.G. Paterson, editors, PAIRING 2008, volume 5209 of LNCS (Springer, 2008), pp. 39\u201356","DOI":"10.1007\/978-3-540-85538-5_3"},{"key":"9249_CR15","doi-asserted-by":"crossref","unstructured":"D.\u00a0Catalano and D.\u00a0Fiore. Practical homomorphic MACs for arithmetic circuits, in T.\u00a0Johansson and P.Q. Nguyen, editors, EUROCRYPT\u00a02013, volume 7881 of LNCS (Springer, 2013), pp. 336\u2013352","DOI":"10.1007\/978-3-642-38348-9_21"},{"key":"9249_CR16","doi-asserted-by":"crossref","unstructured":"D.\u00a0Catalano, D.\u00a0Fiore, R.\u00a0Gennaro, and L.\u00a0Nizzardo. Generalizing homomorphic MACs for arithmetic circuits, in H.\u00a0Krawczyk, editor, PKC\u00a02014, volume 8383 of LNCS (Springer, 2014), pp. 538\u2013555","DOI":"10.1007\/978-3-642-54631-0_31"},{"key":"9249_CR17","doi-asserted-by":"crossref","unstructured":"D.\u00a0Catalano, D.\u00a0Fiore, R.\u00a0Gennaro, and K.\u00a0Vamvourellis. Algebraic (trapdoor) one-way functions and their applications, in A.\u00a0Sahai, editor, TCC\u00a02013, volume 7785 of LNCS (Springer, 2013), pp. 680\u2013699","DOI":"10.1007\/978-3-642-36594-2_38"},{"key":"9249_CR18","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.tcs.2015.05.029","volume":"592","author":"D Catalano","year":"2015","unstructured":"D.\u00a0Catalano, D.\u00a0Fiore, R.\u00a0Gennaro, and K.\u00a0Vamvourellis. Algebraic (trapdoor) one-way functions: Constructions and applications. Theoretical Computer Science, 592:143\u2013165, 2015.","journal-title":"Theor. Comput. Sci."},{"key":"9249_CR19","doi-asserted-by":"crossref","unstructured":"D.\u00a0Catalano, D.\u00a0Fiore, and L.\u00a0Nizzardo. Programmable hash functions go private: Constructions and application to (homomorphic) signatures with shorter public keys, in Advances in Cryptology\u2014CRYPTO\u00a02015\u201435th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16\u201320, 2015, Proceedings, Part II, volume 9216 of LNCS (Springer, 2015), pp. 254\u2013274","DOI":"10.1007\/978-3-662-48000-7_13"},{"key":"9249_CR20","doi-asserted-by":"crossref","unstructured":"D.\u00a0Catalano, D.\u00a0Fiore, and B.\u00a0Warinschi. Adaptive pseudo-free groups and applications, in K.G. Paterson, editor, EUROCRYPT\u00a02011, volume 6632 of LNCS (Springer, 2011), pp. 207\u2013223","DOI":"10.1007\/978-3-642-20465-4_13"},{"key":"9249_CR21","doi-asserted-by":"crossref","unstructured":"D.\u00a0Catalano, D.\u00a0Fiore, and B.\u00a0Warinschi. Efficient network coding signatures in the standard model, in M.\u00a0Fischlin, J.\u00a0Buchmann, and M.\u00a0Manulis, editors, PKC\u00a02012, volume 7293 of LNCS (Springer, 2012), pp. 680\u2013696","DOI":"10.1007\/978-3-642-30057-8_40"},{"key":"9249_CR22","doi-asserted-by":"crossref","unstructured":"D.\u00a0Catalano, D.\u00a0Fiore, and B.\u00a0Warinschi. Homomorphic signatures with efficient verification for polynomial functions, in J.A. Garay and R.\u00a0Gennaro, editors, CRYPTO\u00a02014, Part I, volume 8616 of LNCS (Springer, 2014), pp. 371\u2013389","DOI":"10.1007\/978-3-662-44371-2_21"},{"key":"9249_CR23","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, Y.\u00a0Kalai, and S.\u00a0P. Vadhan. Improved delegation of computation using fully homomorphic encryption, in T.\u00a0Rabin, editor, CRYPTO\u00a02010, volume 6223 of LNCS (Springer, 2010), pp. 483\u2013501","DOI":"10.1007\/978-3-642-14623-7_26"},{"key":"9249_CR24","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, Y.\u00a0T. Kalai, F.-H. Liu, and R.\u00a0Raz. Memory delegation, in P.\u00a0Rogaway, editor, CRYPTO\u00a02011, volume 6841 of LNCS (Springer, 2011), pp. 151\u2013168","DOI":"10.1007\/978-3-642-22792-9_9"},{"issue":"4","key":"9249_CR25","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"RA DeMillo","year":"1978","unstructured":"R.\u00a0A. DeMillo and R.\u00a0J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193\u2013195, 1978.","journal-title":"Inf. Process. Lett."},{"key":"9249_CR26","doi-asserted-by":"crossref","unstructured":"D.\u00a0Fiore and R.\u00a0Gennaro. Publicly verifiable delegation of large polynomials and matrix computations, with applications, in T.\u00a0Yu, G.\u00a0Danezis, and V.D. Gligor, editors, ACM CCS 12 (ACM Press, 2012), pp. 501\u2013512","DOI":"10.1145\/2382196.2382250"},{"key":"9249_CR27","doi-asserted-by":"crossref","unstructured":"D.\u00a0M. Freeman. Improved security for linearly homomorphic signatures: A generic framework, in M.\u00a0Fischlin, J.\u00a0Buchmann, and M.\u00a0Manulis, editors, PKC\u00a02012, volume 7293 of LNCS (Springer, 2012), pp. 697\u2013714","DOI":"10.1007\/978-3-642-30057-8_41"},{"key":"9249_CR28","doi-asserted-by":"crossref","unstructured":"R.\u00a0Gennaro, C.\u00a0Gentry, and B.\u00a0Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers, in T.\u00a0Rabin, editor, CRYPTO\u00a02010, volume 6223 of LNCS (Springer, 2010), pp. 465\u2013482","DOI":"10.1007\/978-3-642-14623-7_25"},{"key":"9249_CR29","doi-asserted-by":"crossref","unstructured":"R.\u00a0Gennaro, J.\u00a0Katz, H.\u00a0Krawczyk, and T.\u00a0Rabin. Secure network coding over the integers, in P.Q. Nguyen and D.\u00a0Pointcheval, editors, PKC\u00a02010, volume 6056 of LNCS (Springer, 2010), pp. 142\u2013160","DOI":"10.1007\/978-3-642-13013-7_9"},{"key":"9249_CR30","doi-asserted-by":"crossref","unstructured":"R.\u00a0Gennaro and D.\u00a0Wichs. Fully homomorphic message authenticators, in K.\u00a0Sako and P.\u00a0Sarkar, editors, ASIACRYPT\u00a02013, Part II, volume 8270 of LNCS (Springer, 2013), pp. 301\u2013320","DOI":"10.1007\/978-3-642-42045-0_16"},{"key":"9249_CR31","doi-asserted-by":"crossref","unstructured":"C.\u00a0Gentry. Fully homomorphic encryption using ideal lattices, in M.\u00a0Mitzenmacher, editor, 41st ACM STOC (ACM Press, 2009), pp. 169\u2013178","DOI":"10.1145\/1536414.1536440"},{"key":"9249_CR32","doi-asserted-by":"crossref","unstructured":"C.\u00a0Gentry and D.\u00a0Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions, in L.\u00a0Fortnow and S.P. Vadhan, editors, 43rd ACM STOC (ACM Press, 2011), pp. 99\u2013108","DOI":"10.1145\/1993636.1993651"},{"key":"9249_CR33","doi-asserted-by":"crossref","unstructured":"S.\u00a0Goldwasser, Y.T. Kalai, and G.N. Rothblum. Delegating computation: interactive proofs for muggles, in R.E. Ladner and C.\u00a0Dwork, editors, 40th ACM STOC (ACM Press, 2008), pp. 113\u2013122","DOI":"10.1145\/1374376.1374396"},{"key":"9249_CR34","doi-asserted-by":"crossref","unstructured":"S.\u00a0Gorbunov, V.\u00a0Vaikuntanathan, and D.\u00a0Wichs. Leveled fully homomorphic signatures from standard lattices, in 47th ACM STOC (ACM Press, 2015)","DOI":"10.1145\/2746539.2746576"},{"key":"9249_CR35","doi-asserted-by":"crossref","unstructured":"R.\u00a0Johnson, D.\u00a0Molnar, D.X. Song, and D.\u00a0Wagner. Homomorphic signature schemes, in B.\u00a0Preneel, editor, CT-RSA\u00a02002, volume 2271 of LNCS (Springer, 2002), pp. 244\u2013262","DOI":"10.1007\/3-540-45760-7_17"},{"key":"9249_CR36","doi-asserted-by":"crossref","unstructured":"J.\u00a0Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract), in 24th ACM STOC (ACM Press, 1992), pp. 723\u2013732","DOI":"10.1145\/129712.129782"},{"key":"9249_CR37","doi-asserted-by":"crossref","unstructured":"B.\u00a0Libert, T.\u00a0Peters, M.\u00a0Joye, and M.\u00a0Yung. Linearly homomorphic structure-preserving signatures and their applications, in R.\u00a0Canetti and J.A. Garay, editors, CRYPTO\u00a02013, Part II, volume 8043 of LNCS (Springer, 2013), pp. 289\u2013307","DOI":"10.1007\/978-3-642-40084-1_17"},{"key":"9249_CR38","doi-asserted-by":"crossref","unstructured":"S.\u00a0Micali. CS proofs (extended abstracts), in 35th FOCS (IEEE Computer Society Press, 1994), pp. 436\u2013453","DOI":"10.1109\/SFCS.1994.365746"},{"issue":"2","key":"9249_CR39","first-page":"481","volume":"E85\u2013A","author":"S Mitsunari","year":"2002","unstructured":"S.\u00a0Mitsunari, R.\u00a0Sakai, and M.\u00a0Kasahara. A new traitor tracing. IEICE Transactions on Fundamentals, E85-A(2):481\u2013484, 2002.","journal-title":"IEICE Trans. Fundam."},{"key":"9249_CR40","doi-asserted-by":"crossref","unstructured":"B.\u00a0Parno, M.\u00a0Raykova, and V.\u00a0Vaikuntanathan. How to delegate and verify in public: Verifiable computation from attribute-based encryption, in R.\u00a0Cramer, editor, TCC\u00a02012, volume 7194 of LNCS (Springer, 2012), pp. 422\u2013439","DOI":"10.1007\/978-3-642-28914-9_24"},{"key":"9249_CR41","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"J.\u00a0T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27:701\u2013717, 1980.","journal-title":"J. ACM"},{"key":"9249_CR42","doi-asserted-by":"crossref","unstructured":"H.\u00a0Shacham and B.\u00a0Waters. Compact proofs of retrievability, in J.\u00a0Pieprzyk, editor, ASIACRYPT\u00a02008, volume 5350 of LNCS (Springer, 2008), pp. 90\u2013107","DOI":"10.1007\/978-3-540-89255-7_7"},{"issue":"3\u20134","key":"9249_CR43","first-page":"207","volume":"5","author":"A Shpilka","year":"2010","unstructured":"A.\u00a0Shpilka and A.\u00a0Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207\u2013388, 2010.","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"9249_CR44","doi-asserted-by":"crossref","unstructured":"P.\u00a0Valiant. Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency, in R.\u00a0Canetti, editor, TCC\u00a02008, volume 4948 of LNCS (Springer, 2008), pp. 1\u201318","DOI":"10.1007\/978-3-540-78524-8_1"},{"key":"9249_CR45","doi-asserted-by":"crossref","unstructured":"R.\u00a0Zippel. Probabilistic algorithms for sparse polynomials. In E.\u00a0W. Ng, editor, EUROSM \u201979, volume\u00a072 of Lecture Notes in Computer Science (Springer, 1979), pp. 216\u2013226","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/article\/10.1007\/s00145-016-9249-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9249-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9249-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T00:20:01Z","timestamp":1749860401000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/10.1007\/s00145-016-9249-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,4]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9249"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/s00145-016-9249-1","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,4]]},"assertion":[{"value":"13 April 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}