{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T12:06:57Z","timestamp":1743077217659,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662467053"},{"type":"electronic","value":"9783662467060"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46706-0_25","type":"book-chapter","created":{"date-parts":[[2015,4,18]],"date-time":"2015-04-18T02:15:01Z","timestamp":1429323301000},"page":"489-508","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On the Minimum Number of Multiplications Necessary for Universal Hash Functions"],"prefix":"10.1007","author":[{"given":"Mridul","family":"Nandi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,19]]},"reference":[{"key":"25_CR1","first-page":"775","volume":"123","author":"GE Belaga","year":"1958","unstructured":"Belaga, G.E.: Some problems in the computation of polynomials. Doklady Akademii Nauk SSSR 123, 775\u2013777 (1958). ISSN 00023264. Citations in this document: \u00a76","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1007\/11818175_36","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"M Bellare","year":"2006","unstructured":"Bellare, M.: New proofs for NMAC and HMAC: security without collision-resistance. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 602\u2013619. Springer, Heidelberg (2006)"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/3-540-48329-2_28","volume-title":"Advances in Cryptology - CRYPTO \u201993","author":"J Bierbrauer","year":"1994","unstructured":"Bierbrauer, J., Johansson, T., Kabatianskii, G.A., Smeets, B.J.M.: On families of hash functions via geometric codes and concatenation. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 331\u2013342. Springer, Heidelberg (1994)"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-48405-1_14","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"J Black","year":"1999","unstructured":"Black, J., Halevi, S., Krawczyk, H., Krovetz, T., Rogaway, P.: UMAC: fast and secure message authentication. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 216\u2013233. Springer, Heidelberg (1999). Citations in this document: \u00a71, \u00a71.1"},{"issue":"2","key":"25_CR5","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1109\/18.485722","volume":"42","author":"M Blaum","year":"1996","unstructured":"Blaum, M., Bruck, J., Vardy, A.: MDS array codes with independent parity symbols. IEEE Trans. Inf. Theor. 42(2), 529\u2013542 (1996). Citations in this document: \u00a74.1","journal-title":"IEEE Trans. Inf. Theor."},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/11502760_3","volume-title":"Fast Software Encryption","author":"DJ Bernstein","year":"2005","unstructured":"Bernstein, D.J.: The Poly1305-AES message-authentication code. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 32\u201349. Springer, Heidelberg (2005). Citations in this document: \u00a71, \u00a73.1"},{"key":"25_CR7","unstructured":"Bernstein, D.J.: Polynomial evaluation and message authentication. URL: http:\/\/cr.yp.to\/papers.html#pema . ID b1ef3f2d385a926123e 1517392e20f8c (2007)"},{"key":"25_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/11496137_13","volume-title":"Applied Cryptography and Network Security","author":"M Boesgaard","year":"2005","unstructured":"Boesgaard, M., Christensen, T., Zenner, E.: Badger \u2013 a fast and provably secure MAC. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 176\u2013191. Springer, Heidelberg (2005)"},{"key":"25_CR9","first-page":"65","volume":"2","author":"B Boer den","year":"1993","unstructured":"den Boer, B.: A simple and key-economical unconditional authentication scheme. J. Comput. Secur. 2, 65\u201371 (1993)","journal-title":"J. Comput. Secur."},{"issue":"2","key":"25_CR10","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L Carter","year":"1979","unstructured":"Carter, L., Wegman, N.M.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-48405-1_15","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"M Etzel","year":"1999","unstructured":"Etzel, M., Patel, S., Ramzan, Z.: Square hash: fast message authentication via optimized universal hash functions. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 234\u2013251. Springer, Heidelberg (1999). Citations in this document: \u00a72"},{"key":"25_CR12","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01386049","volume":"6","author":"J Eve","year":"1964","unstructured":"Eve, J.: The evaluation of polynomials. Numer. Math. 6, 17\u201321 (1964). Citations in this document: \u00a76","journal-title":"Numer. Math."},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1002\/j.1538-7305.1974.tb02751.x","volume":"53","author":"NE Gilbert","year":"1974","unstructured":"Gilbert, N.E., MacWilliams, F.J., Neil, J.A.: Sloane, Codes which detect deception. Bell Syst. Tech. J. 53, 405\u2013424 (1974)","journal-title":"Bell Syst. Tech. J."},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/BFb0052345","volume-title":"Fast Software Encryption","author":"S Halevi","year":"1997","unstructured":"Halevi, S., Krawczyk, H.: MMH: software message authentication in the Gbit\/second rates. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 172\u2013189. Springer, Heidelberg (1997). Citations in this document: \u00a71.1, \u00a71.1, \u00a73.1, \u00a73.3"},{"issue":"4","key":"25_CR15","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J Hastad","year":"1999","unstructured":"Hastad, J., Impagliazzo, R., Levin, L.A., Luby, M.: Construction of pseudorandom generators from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"25_CR16","first-page":"308","volume":"109","author":"WG Horner","year":"1819","unstructured":"Horner, W.G.: Philosophical transactions. Roy. Soc. Lond. 109, 308\u2013335 (1819). Citations in this document: \u00a76","journal-title":"Roy. Soc. Lond."},{"key":"25_CR17","first-page":"433","volume":"2008","author":"Y Ishai","year":"2008","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. STOC 2008, 433\u2013442 (2008). Citations in this document: \u00a71.1, \u00a71.1","journal-title":"STOC"},{"key":"25_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-69053-0_12","volume-title":"Advances in Cryptology - EUROCRYPT \u201997","author":"T Johansson","year":"1997","unstructured":"Johansson, T.: Bucket hashing with a small key size. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 149\u2013162. Springer, Heidelberg (1997)"},{"issue":"12","key":"25_CR19","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1109\/TC.2005.195","volume":"54","author":"J Kaps","year":"2005","unstructured":"Kaps, J., Y\u00fcksel, K., Sunar, B.: Energy scalable universal hashing. IEEE Trans. Comput. 54(12), 1484\u20131495 (2005)","journal-title":"IEEE Trans. Comput."},{"key":"25_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-540-25937-4_26","volume-title":"Fast Software Encryption","author":"T Kohno","year":"2004","unstructured":"Kohno, T., Viega, J., Whiting, D.: CWC: a high-performance conventional authenticated encryption mode. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 408\u2013426. Springer, Heidelberg (2004)"},{"key":"25_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-540-74462-7_23","volume-title":"Selected Areas in Cryptography","author":"T Krovetz","year":"2007","unstructured":"Krovetz, T.: Message authentication on 64-bit architectures. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 327\u2013341. Springer, Heidelberg (2007)"},{"key":"25_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/978-3-540-30556-9_27","volume-title":"Progress in Cryptology - INDOCRYPT 2004","author":"DA McGrew","year":"2004","unstructured":"McGrew, D.A., Viega, J.: The security and performance of the Galois\/Counter mode (GCM) of operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 343\u2013355. Springer, Heidelberg (2004). Citations in this document: \u00a73.1"},{"key":"25_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/3-540-48658-5_15","volume-title":"Advances in Cryptology - CRYPTO \u201994","author":"H Krawczyk","year":"1994","unstructured":"Krawczyk, H.: LFSR-based hashing and authentication. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 129\u2013139. Springer, Heidelberg (1994). Citations in this document: \u00a72, \u00a73.5"},{"key":"25_CR24","volume-title":"The Art of Programming","author":"D Knuth","year":"1969","unstructured":"Knuth, D.: The Art of Programming. Addison-Wesley, Boston (1969). Citations in this document: \u00a71, \u00a76"},{"key":"25_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-45247-8_7","volume-title":"Information Security and Cryptology - ICISC 2000","author":"T Krovetz","year":"2001","unstructured":"Krovetz, T., Rogaway, P.: Fast universal hashing with small keys and no preprocessing: the PolyR construction. In: Won, D. (ed.) ICISC 2000. LNCS, vol. 2015, pp. 73\u201389. Springer, Heidelberg (2001). Citations in this document: \u00a73.1"},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"Mansour, Y., Nissan, N., Tiwari, P.: The computational complexity of universal hashing. In: Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing (1990), pp. 235\u2013243. ACM Press (1990) Citations in this document: \u00a71.1","DOI":"10.1145\/100216.100246"},{"key":"25_CR27","volume-title":"The Theory of Error-Correcting Codes","author":"FJ MacWilliams","year":"1977","unstructured":"MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. Elsevier, North-Holland (1977). Citations in this document: \u00a71.1"},{"key":"25_CR28","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: On the program size of perfect and universal hash functions. In: FOCS, pp. 170\u2013175 (1982)","DOI":"10.1109\/SFCS.1982.80"},{"key":"25_CR29","first-page":"163","volume":"61","author":"TS Motzkin","year":"1955","unstructured":"Motzkin, T.S.: Evaluation of polynomials and evaluation of rational functions. Bull Xmer. Math SOC. 61, 163 (1955). Citations in this document: \u00a76, \u00a76","journal-title":"Bull Xmer. Math SOC."},{"key":"25_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/3-540-48910-X_3","volume-title":"Advances in Cryptology - EUROCRYPT \u201999","author":"W Nevelsteen","year":"1999","unstructured":"Nevelsteen, W., Preneel, B.: Software performance of universal hash functions. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 24. Springer, Heidelberg (1999)"},{"key":"25_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-642-34047-5_19","volume-title":"Fast Software Encryption","author":"LH Nguyen","year":"2012","unstructured":"Nguyen, L.H., Roscoe, A.W.: Short-output universal hash functions and their use in fast and secure data authentication. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 326\u2013345. Springer, Heidelberg (2012). Citations in this document: \u00a73.5"},{"issue":"1","key":"25_CR32","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N Nisan","year":"1996","unstructured":"Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Comput. Syst. Sci. 52(1), 43\u201353 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR33","series-title":"Studies Presented to R. von Mises","volume-title":"On two problems in abstract algebra connected with Homers rule","author":"AM Ostrowski","year":"1954","unstructured":"Ostrowski, A.M.: On two problems in abstract algebra connected with Homers rule. Studies Presented to R. von Mises. Academic Press, New York (1954). Citations in this document: \u00a76"},{"key":"25_CR34","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1070\/RM1966v021n01ABEH004147","volume":"21","author":"V Ya","year":"1966","unstructured":"Ya, V.: Pan, Methods of computing values of polynomials. Russ. Math. Surv. 21, 105\u2013136 (1966). Citations in this document: \u00a76, \u00a76, \u00a76","journal-title":"Russ. Math. Surv."},{"issue":"1","key":"25_CR35","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/0202007","volume":"2","author":"MS Paterson","year":"1973","unstructured":"Paterson, M.S., Stockmeyer, L.J.: On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2(1), 60\u201366 (1973). Citations in this document: \u00a76, \u00a76","journal-title":"SIAM J. Comput."},{"key":"25_CR36","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1002\/cpa.3160250405","volume":"XXV","author":"MO Rabin","year":"1972","unstructured":"Rabin, M.O., Winograd, S.: Fast evaluation of polynomials by rational preparation. Commun. Pure Appl. Math. XXV, 433\u2013458 (1972). Citations in this document: \u00a76","journal-title":"Commun. Pure Appl. Math."},{"issue":"2","key":"25_CR37","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/PL00003822","volume":"12","author":"P Rogaway","year":"1999","unstructured":"Rogaway, P.: Bucket hashing and its application to fast message authentication. J. Cryptology. 12(2), 91\u2013115 (1999). Citations in this document: \u00a72, \u00a73.5","journal-title":"J. Cryptology."},{"key":"25_CR38","first-page":"1","volume":"69","author":"P Sarkar","year":"2012","unstructured":"Sarkar, P.: A new multi-linear universal hash family. Des. Codes Crypt. 69, 1\u201317 (2012). Springer. Citations in this document: \u00a73.5, \u00a73.5","journal-title":"Des. Codes Crypt."},{"key":"25_CR39","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10623-010-9408-6","volume":"3","author":"P Sarkar","year":"2011","unstructured":"Sarkar, P.: A trade-off between collision probability and key size in universal hashing using polynomials. Des. Codes Crypt. 3, 271\u2013278 (2011)","journal-title":"Des. Codes Crypt."},{"key":"25_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/3-540-68697-5_24","volume-title":"Advances in Cryptology - CRYPTO \u201996","author":"V Shoup","year":"1996","unstructured":"Shoup, V.: On fast and provably secure message authentication based on universal hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 313\u2013328. Springer, Heidelberg (1996). Citations in this document: \u00a73.2, \u00a73.5"},{"issue":"4","key":"25_CR41","first-page":"388","volume":"4","author":"DA Spielman","year":"1995","unstructured":"Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. STOC 1995 4(4), 388\u2013397 (1995). Citations in this document: \u00a71.1","journal-title":"STOC 1995"},{"issue":"4","key":"25_CR42","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF01388651","volume":"4","author":"D Stinson","year":"1994","unstructured":"Stinson, D.: Universal hashing and authentication codes. Des. Codes Crypt. 4(4), 369\u2013380 (1994)","journal-title":"Des. Codes Crypt."},{"key":"25_CR43","first-page":"7","volume":"114","author":"DR Stinson","year":"1996","unstructured":"Stinson, D.R.: On the connections between universal hashing, combinatorial designs and error-correcting codes. Proc. Congressus Numerantium 114, 7\u201327 (1996). Citations in this document: \u00a72, \u00a72, \u00a77","journal-title":"Proc. Congressus Numerantium"},{"key":"25_CR44","unstructured":"Stinson, D.R.: Universal Hash Families and the Leftover Hash Lemma, and Applications to Cryptography and Computing. Research report (University of Waterloo. Faculty of Mathematics) (2001). http:\/\/books.google.co.in\/books?id=edldNAEACAAJ Citations in this document: \u00a71"},{"key":"25_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/3-540-48329-2_4","volume-title":"Advances in Cryptology - CRYPTO \u201993","author":"R Taylor","year":"1994","unstructured":"Taylor, R.: An integrity check value algorithm for stream ciphers. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 40\u201348. Springer, Heidelberg (1994)"},{"key":"25_CR46","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1109\/TC.1968.227420","volume":"17","author":"S Winograd","year":"1968","unstructured":"Winograd, S.: A new algorithm for inner product. IEEE Trans. Comput. 17, 693\u2013694 (1968). Citations in this document: \u00a71.1, \u00a73.3","journal-title":"IEEE Trans. Comput."},{"key":"25_CR47","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/cpa.3160230204","volume":"XXIII","author":"S Winograd","year":"1970","unstructured":"Winograd, S.: On the number of multiplications necessary to compute certain functions. Commun. Pure Appl. Math. XXIII, 165\u2013179 (1970). Citations in this document: \u00a71, \u00a76","journal-title":"Commun. Pure Appl. Math."},{"issue":"5","key":"25_CR48","doi-asserted-by":"publisher","first-page":"1840","DOI":"10.1073\/pnas.58.5.1840","volume":"58","author":"S Winograd","year":"1967","unstructured":"Winograd, S.: On the number of multiplications required to compute certain functions. Proc. National Acad. Sci. USA 58(5), 1840\u20131842 (1967)","journal-title":"Proc. National Acad. Sci. USA"},{"issue":"22","key":"25_CR49","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","volume":"1981","author":"M Wegman","year":"1981","unstructured":"Wegman, M., Carter, L.: New hash functions and their use in authentication and set equality. J. of Comp. Syst. Sci. 1981(22), 265\u2013279 (1981)","journal-title":"J. of Comp. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Fast Software Encryption"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46706-0_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,5]],"date-time":"2022-05-05T12:20:25Z","timestamp":1651753225000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46706-0_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662467053","9783662467060"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46706-0_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"19 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}