{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:41:00Z","timestamp":1767919260244,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662538890","type":"print"},{"value":"9783662538906","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-53890-6_17","type":"book-chapter","created":{"date-parts":[[2016,11,8]],"date-time":"2016-11-08T12:11:32Z","timestamp":1478607092000},"page":"499-530","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":40,"title":["Multi-key Homomorphic Authenticators"],"prefix":"10.1007","author":[{"given":"Dario","family":"Fiore","sequence":"first","affiliation":[]},{"given":"Aikaterini","family":"Mitrokotsa","sequence":"additional","affiliation":[]},{"given":"Luca","family":"Nizzardo","sequence":"additional","affiliation":[]},{"given":"Elena","family":"Pagnin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,11,9]]},"reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-642-13013-7_10","volume-title":"Public Key Cryptography \u2013 PKC 2010","author":"S Agrawal","year":"2010","unstructured":"Agrawal, S., Boneh, D., Boyen, X., Freeman, D.M.: Preventing pollution attacks in multi-source network coding. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 161\u2013176. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-13013-7_10"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: 28th ACM STOC, pp. 99\u2013108. ACM Press, May 1996","DOI":"10.1145\/237814.237838"},{"key":"17_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-48523-6_1","volume-title":"Automata, Languages and Programming","author":"M Ajtai","year":"1999","unstructured":"Ajtai, M.: Generating hard instances of the short basis problem. In: Wiedermann, J., Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 1\u20139. Springer, Heidelberg (1999). doi:10.1007\/3-540-48523-6_1"},{"issue":"3","key":"17_CR4","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s00224-010-9278-3","volume":"48","author":"J Alwen","year":"2011","unstructured":"Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. Theory Comput. Syst. 48(3), 535\u2013553 (2011)","journal-title":"Theory Comput. Syst."},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Backes, M., Fiore, D., Reischuk, R.M.: Verifiable delegation of computation on outsourced data. In: Sadeghi, A.-R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 863\u2013874. ACM Press, November 2013","DOI":"10.1145\/2508859.2516681"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-22792-9_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"S Benabbas","year":"2011","unstructured":"Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable delegation of computation over large datasets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 111\u2013131. Springer, Heidelberg (2011). doi:10.1007\/978-3-642-22792-9_7"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKS and proof-carrying data. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 111\u2013120. ACM Press, June 2013","DOI":"10.1145\/2488608.2488623"},{"key":"17_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-642-00468-1_5","volume-title":"Public Key Cryptography \u2013 PKC 2009","author":"D Boneh","year":"2009","unstructured":"Boneh, D., Freeman, D., Katz, J., Waters, B.: Signing a linear subspace: signature schemes for network coding. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 68\u201387. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-00468-1_5"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-642-20465-4_10","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"D Boneh","year":"2011","unstructured":"Boneh, D., Freeman, D.M.: Homomorphic signatures for polynomial functions. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 149\u2013168. Springer, Heidelberg (2011). doi:10.1007\/978-3-642-20465-4_10"},{"key":"17_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-642-55220-5_30","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"D Boneh","year":"2014","unstructured":"Boneh, D., Gentry, C., Gorbunov, S., Halevi, S., Nikolaenko, V., Segev, G., Vaikuntanathan, V., Vinayagamurthy, D.: Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 533\u2013556. Springer, Heidelberg (2014). doi:10.1007\/978-3-642-55220-5_30"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-642-38348-9_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"D Catalano","year":"2013","unstructured":"Catalano, D., Fiore, D.: Practical homomorphic MACs for arithmetic circuits. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 336\u2013352. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-38348-9_21"},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1007\/978-3-642-54631-0_31","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"D Catalano","year":"2014","unstructured":"Catalano, D., Fiore, D., Gennaro, R., Nizzardo, L.: Generalizing homomorphic MACs for arithmetic circuits. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 538\u2013555. Springer, Heidelberg (2014). doi:10.1007\/978-3-642-54631-0_31"},{"key":"17_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/978-3-662-48000-7_13","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"D Catalano","year":"2015","unstructured":"Catalano, D., Fiore, D., Nizzardo, L.: Programmable hash functions go private: constructions and applications to (homomorphic) signatures with shorter public keys. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 254\u2013274. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-48000-7_13"},{"key":"17_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-20465-4_13","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"D Catalano","year":"2011","unstructured":"Catalano, D., Fiore, D., Warinschi, B.: Adaptive pseudo-free groups and applications. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 207\u2013223. Springer, Heidelberg (2011). doi:10.1007\/978-3-642-20465-4_13"},{"key":"17_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1007\/978-3-642-30057-8_40","volume-title":"Public Key Cryptography \u2013 PKC 2012","author":"D Catalano","year":"2012","unstructured":"Catalano, D., Fiore, D., Warinschi, B.: Efficient network coding signatures in the standard model. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 680\u2013696. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-30057-8_40"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-662-44371-2_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2014","author":"D Catalano","year":"2014","unstructured":"Catalano, D., Fiore, D., Warinschi, B.: Homomorphic signatures with efficient verification for polynomial functions. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 371\u2013389. Springer, Heidelberg (2014). doi:10.1007\/978-3-662-44371-2_21"},{"key":"17_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-642-36594-2_28","volume-title":"Theory of Cryptography","author":"SG Choi","year":"2013","unstructured":"Choi, S.G., Katz, J., Kumaresan, R., Cid, C.: Multi-client non-interactive verifiable computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 499\u2013518. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-36594-2_28"},{"key":"17_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-14623-7_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"K-M Chung","year":"2010","unstructured":"Chung, K.-M., Kalai, Y., Vadhan, S.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483\u2013501. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-14623-7_26"},{"issue":"1","key":"17_CR19","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/060651380","volume":"38","author":"Y Dodis","year":"2008","unstructured":"Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97\u2013139 (2008)","journal-title":"SIAM J. Comput."},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 2012, pp. 501\u2013512. ACM Press, October 2012","DOI":"10.1145\/2382196.2382250"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"Fiore, D., Gennaro, R., Pastro, V.: Efficiently verifiable computation on encrypted data. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 844\u2013855. ACM Press, November 2014","DOI":"10.1145\/2660267.2660366"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Fiore, D., Mitrokotsa, A., Nizzardo, L., Pagnin, E.: Multi-key homomorphic authenticators. IACR Cryptology ePrint Archive (2016)","DOI":"10.1007\/978-3-662-53890-6_17"},{"key":"17_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1007\/978-3-642-30057-8_41","volume-title":"Public Key Cryptography \u2013 PKC 2012","author":"DM Freeman","year":"2012","unstructured":"Freeman, D.M.: Improved security for linearly homomorphic signatures: a generic framework. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 697\u2013714. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-30057-8_41"},{"key":"17_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/b102438","volume-title":"Algorithms for Computer Algebra","author":"KO Geddes","year":"1992","unstructured":"Geddes, K.O., Czapor, S.R., Labahn, G.: Algorithms for Computer Algebra. Kluwer Academic Publishers, Norwell (1992)"},{"key":"17_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-14623-7_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"R Gennaro","year":"2010","unstructured":"Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465\u2013482. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-14623-7_25"},{"key":"17_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-42045-0_16","volume-title":"Advances in Cryptology - ASIACRYPT 2013","author":"R Gennaro","year":"2013","unstructured":"Gennaro, R., Wichs, D.: Fully homomorphic message authenticators. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 301\u2013320. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-42045-0_16"},{"key":"17_CR27","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169\u2013178. ACM Press, May\/June 2009","DOI":"10.1145\/1536414.1536440"},{"key":"17_CR28","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197\u2013206. ACM Press, May 2008","DOI":"10.1145\/1374376.1374407"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 113\u2013122. ACM Press, May 2008","DOI":"10.1145\/1374376.1374396"},{"key":"17_CR30","doi-asserted-by":"crossref","unstructured":"Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th ACM STOC, pp. 469\u2013477. ACM Press, June 2015","DOI":"10.1145\/2746539.2746576"},{"key":"17_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-662-46497-7_6","volume-title":"Theory of Cryptography","author":"SD Gordon","year":"2015","unstructured":"Gordon, S.D., Katz, J., Liu, F.-H., Shi, E., Zhou, H.-S.: Multi-client verifiable computation with stronger security guarantees. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 144\u2013168. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-46497-7_6"},{"key":"17_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/3-540-45760-7_17","volume-title":"Topics in Cryptology \u2014 CT-RSA 2002","author":"R Johnson","year":"2002","unstructured":"Johnson, R., Molnar, D., Song, D., Wagner, D.: Homomorphic signature schemes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 244\u2013262. Springer, Heidelberg (2002). doi:10.1007\/3-540-45760-7_17"},{"issue":"1","key":"17_CR33","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1137\/S0097539703433511","volume":"34","author":"Daniele Micciancio","year":"2004","unstructured":"Micciancio, D.: Almost perfect lattices, the covering radius problem, applications to Ajtai\u2019s connection factor. SIAM J. Comput. 34(1), 118\u2013169 (2004). Preliminary version in STOC 2002","journal-title":"SIAM Journal on Computing"},{"key":"17_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1007\/978-3-642-29011-4_41","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"D Micciancio","year":"2012","unstructured":"Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700\u2013718. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-29011-4_41"},{"key":"17_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-642-40041-4_2","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"D Micciancio","year":"2013","unstructured":"Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 21\u201339. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-40041-4_2"},{"key":"17_CR36","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. In: 45th FOCS, pp. 372\u2013381. IEEE Computer Society Press, October 2004","DOI":"10.1109\/FOCS.2004.72"},{"key":"17_CR37","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-642-28914-9_24","volume-title":"Theory of Cryptography","author":"B Parno","year":"2012","unstructured":"Parno, B., Raykova, M., Vaikuntanathan, V.: How to delegate and verify in public: verifiable computation from attribute-based encryption. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 422\u2013439. Springer, Heidelberg (2012)"},{"key":"17_CR38","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.jsc.2012.06.004","volume":"50","author":"J van der Hoeven","year":"2013","unstructured":"van der Hoeven, J., Lecerf, G.: On the bit-complexity of sparse polynomial and series multiplication. J. Symbolic Comput. 50, 227\u2013254 (2013)","journal-title":"J. Symbolic Comput."}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 ASIACRYPT 2016"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53890-6_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T04:48:07Z","timestamp":1749703687000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-53890-6_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662538890","9783662538906"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53890-6_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"9 November 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ASIACRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Theory and Application of Cryptology and Information Security","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hanoi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vietnam","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 December 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"asiacrypt2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.asiacrypt2016.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}