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.