Bucket hashing and its application to fast message authentication
type: Item
instance of: scholarly article
title: Bucket hashing and its application to fast message authentication
zbMATH Open document ID: 0937.94011
DOI: 10.1007/PL00003822
author: Phillip Rogaway
published in: Journal of Cryptology
publication date: 2000-06-06T00:00:00Z
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.
Mathematics Subject Classification ID: 94A62
Mathematics Subject Classification ID: 68P25
zbMATH DE Number: 1299975
zbMATH Keywords: message authentication code
zbMATH Keywords: universal hashing
zbMATH Keywords: almost universal hash functions
zbMATH Keywords: bucket hashing
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
full work available at URL: pl00003822
OpenAlex ID: W2022640260
description: scientific article; zbMATH DE number 1299975