Short-output universal hash functions and their use in fast and secure data authentication

Journal article

Message authentication codes usually require the underlining universal hash functions to have a long output so that the probability of successfully forging messages is low enough for cryptographic purposes. To take advantage of fast operation on word-size parameters in modern processors, long-output universal hashing schemes can be securely constructed by concatenating several different instances of a short-output primitive. In this paper, we describe a new method for short-output universal hash function termed digest() suitable for very fast software implementation and applicable to secure message authentication. The method possesses a higher level of security relative to other well-studied and computationally efficient short-output universal hashing schemes. Suppose that the universal hash output is fixed at one word of b bits, then the collision probability of ours is 2 1-b compared to 6 × 2 -b of MMH, whereas 2 -b/2 of NH within UMAC is far away from optimality. In addition to message authentication codes, we show how short-output universal hashing is applicable to manual authentication protocols where universal hash keys are used in a very different and interesting way. © 2012 Springer-Verlag.

Authors: Nguyen, L; Roscoe, A

• Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
• Volume: 7549 LNCS
• Pages: 326-345
• Publication date: 2012-01-01
• DOI: 10.1007/978-3-642-34047-5_19
• EISSN: 1611-3349
• ISSN: 0302-9743
• Language: English