Abstract
Universal hash functions are important building blocks for unconditionally secure message authentication codes. In this paper, we present a new construction of a class of ε-Almost Strongly Universal2 hash functions with much smaller description (or key) length than the Wegman-Carter construction. Unlike some other constructions, our new construction has a very short key length and a security parameter ε that is independent of the message length, which makes it suitable for authentication in practical applications such as Quantum Cryptography.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Atici, M., Stinson, D.R.: Universal Hashing and Multiple Authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 16–30. Springer, Heidelberg (1996)
Bennett, C.H., Brassard, G.: Quantum cryptography: Public key distribution and coin tossing. In: Proc. IEEE Int. Conf. Comput. Syst. Signal Process., Bangalore, India, pp. 175–179 (1984)
Bierbrauer, J., Johansson, T., Kabatianskii, G., Smeets, B.: On Families of Hash Functions via Geometric Codes and Concatenation. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 331–342. Springer, Heidelberg (1994)
Black, J.: Message authentication codes. Ph.D. thesis, University of California Davis, USA (2000)
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–233. Springer, Heidelberg (1999)
den Boer, B.: A simple and key-economical unconditional authentication scheme. J. Comp. Sec. 2, 65–72 (1993)
Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18, 143–154 (1979)
Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J., Knuth, D.E.: On the Lambert W function. Adv. Comput. Math. 5, 329–359 (1996)
Gemmell, P., Naor, M.: Codes for Interactive Authentication. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 355–367. Springer, Heidelberg (1994)
Halevi, S., Krawczyk, H.: MMH: Software Message Authentication in the Gbit/Second Rates. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 172–189. Springer, Heidelberg (1997)
Johansson, T.: Bucket Hashing with a Small Key Size. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 149–162. Springer, Heidelberg (1997)
Kabatianskii, G., Smeets, B.J.M., Johansson, T.: On the cardinality of systematic authentication codes via error-correcting codes. IEEE Trans. Inf. Theory 42, 566–578 (1996)
Krawczyk, H.: LFSR-Based Hashing and Authentication. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 129–139. Springer, Heidelberg (1994)
Krawczyk, H.: New Hash Functions for Message Authentication. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 301–310. Springer, Heidelberg (1995)
Mansour, Y., Nisan, N., Tiwari, P.: The computational complexity of universal hashing. In: Ortiz, H. (ed.) Proc. STOC 1990, pp. 235–243. ACM, New York (1990)
Nguyen, L.H., Roscoe, A.W.: A new bound for t-wise almost universal hash functions. IACR Cryptology ePrint Archive, Report 2009/153 (2009), http://eprint.iacr.org/2009/153
Preneel, B.: Analysis and design of cryptographic hash functions. Ph.D. thesis, Katholieke Universiteit Leuven, Belgium (1993)
Rogaway, P.: Bucket Hashing and Its Application to Fast Message Authentication. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 29–42. Springer, Heidelberg (1995)
Shor, P.W., Preskill, J.: Simple proof of security of the bb84 quantum key distribution protocol. Phys. Rev. Lett. 85, 441–444 (2000)
Stinson, D.R.: Universal Hashing and Authentication Codes. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 74–85. Springer, Heidelberg (1992)
Stinson, D.R.: Combinatorial techniques for universal hashing. J. Comput. Syst. Sci. 48, 337–346 (1994)
Stinson, D.R.: On the connections between universal hashing, combinatorial designs and error-correcting codes. Congressus Numerantium 114, 7–27 (1996)
Stinson, D.R.: Universal hash families and the leftover hash lemma, and applications to cryptography and computing. J. Combin. Math. Combin. Comput. 42, 3–31 (2002)
Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22, 265–279 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abidin, A., Larsson, JÅ. (2012). New Universal Hash Functions. In: Armknecht, F., Lucks, S. (eds) Research in Cryptology. WEWoRC 2011. Lecture Notes in Computer Science, vol 7242. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34159-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-34159-5_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34158-8
Online ISBN: 978-3-642-34159-5
eBook Packages: Computer ScienceComputer Science (R0)