D. J. Bernstein
Fighting patents

US patent 5673318, Bellare Guerin Rogaway, message authentication

Text of the patent
No reports of enforcement attempts.

The central idea of this patent is a reinvention of a hash function published by Zobrist in 1970. Zobrist's hash of a string c[1], c[2], ..., c[n] is r[1][c[1]] + r[2][c[2]] + ... + r[n][c[n]], where each r[i][j] is a uniform random number:

Consider the problem of hashing English words of ten characters or less. The set S could be the 260 elements of the form: ... For example: hash(CAT) = h_{3,1} XOR h_{1,2} XOR h_{20,3} ...
Zobrist observed that this hash function has uniform differences.

Wegman and Carter in 1981 pointed out a general mechanism to authenticate messages using any hash function with uniform differences. They gave several examples of these hash functions, and a very general construction that obviously includes Zobrist's hash function, although they did not know about Zobrist's work.

It is a completely standard technique in cryptography to replace uniform random functions with conjecturally unpredictable low-entropy random functions. Instead of sharing a long string of random numbers, the sender and receiver share a short key, and use an encryption function as a random number generator. This transformation is now considered obvious; in the case of the Wegman-Carter system, it was pointed out explicitly by Brassard in 1982.

Brassard's system, with Zobrist's hash function, is exactly the Bellare-Guerin-Rogaway system.