Bucket hashing and its application to fast message authentication

DOI10.1007/PL00003822MaRDI QIDQ1291805zbMATH OpenOpenAlexFDO

Authors Phillip Rogaway

Publication date 6 June 2000

Published in Journal of Cryptology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00003822

zbMATH Keywords

almost universal hash functionsbucket hashingmessage authentication codeuniversal hashing

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Authentication, digital signatures and secret sharing (94A62)

Review text

A message authentication code (MAC) is often used to provide message authentication. Usually MAC generation and verification need to be done in software, i.e. frequent MAC computations over long strings call for fast techniques. Often, cryptographic hash functions are used to compute a MAC, however as shown by \textit{M. N. Wegman} and \textit{J. L. Carter} [J. Comput. Syst. Sci. 22, 265-279 (1981; Zbl 0461.68074)] it is not necessary to ``cryptographically transform the whole string (message). In this framework the problem of constructing a fast-to-compute MAC can be reduced to finding a family of almost universal hash functions whose members can be computed in a fast way. In the paper a new technique to construct a family of almost universal hash functions, called bucket hashing is introduced thus providing an extremely fast method to compute a MAC. After an introduction and survey of previous and subsequent work in the area, necessary definitions and basic properties of universal hash families are reviewed. Then bucket hashing is introduced and a particular bucket hashing scheme is analyzed and a detailed proof of the main theorem on upper bounds of the collision probability is given. In the second part of the paper the Wegman-Carter construction of a MAC from a given family of hash functions is reviewed, followed by an example of a concrete MAC based on the ideas of bucket hashing described in the previous sections. This example is also used to discuss some of the difficulties involved in constructing MAC using bucket hashing. Finally possible extensions of the approach are discussed and some open questions outlined.

Recommendations

• scientific article; zbMATH DE number 1030979
• scientific article; zbMATH DE number 1418298
• scientific article; zbMATH DE number 1030977
• MMH: Software message authentication in the Gbit/second rates

Cited in

(17)

• The circulant hash revisited
• Tight security of cascaded LRW2
• A trade-off between collision probability and key size in universal hashing using polynomials
• SipHash: a fast short-input PRF
• Analysis of the Initial and Modified Versions of the Candidate 3GPP Integrity Algorithm 128-EIA3
• \(\Gamma\)-MAC\([H,P]\) -- a new universal MAC scheme
• Badger – A Fast and Provably Secure MAC
• A new multi-linear universal hash family
• The universality of iterated hashing over variable-length strings
• Software Performance of Universal Hash Functions
• scientific article; zbMATH DE number 1030979 (Why is no real title available?)
• scientific article; zbMATH DE number 1962142 (Why is no real title available?)
• scientific article; zbMATH DE number 1980973 (Why is no real title available?)
• Fast message authentication using efficient polynomial evaluation
• scientific article; zbMATH DE number 1418298 (Why is no real title available?)
• Secure mutual authentication quantum key agreement scheme for two-party setting with key recycling
• A construction method for optimally universal hash families and its consequences for the existence of RBIBDs

This page was built for publication: Bucket hashing and its application to fast message authentication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1291805)