DIMACS Special Year on Networks Seminar


Small Biased Toeplitz Hashing with Applications to Message Authentication


Hugo Krawczyk
IBM - T.J. Watson Research Center


AT&T Murray Hill Building, Room: 2A-435
Note: If you are not from the MH building, then enter the building at Stair 9, which is on the east side of the building, no later than 2:15. AT&T Host: Mike Reiter.


2:30 - 3:30 p.m
Friday, November 22, 1996

We show how to construct almost universal hashing using Toeplitz matrices generated out of small biased sequences. This leads to simple and efficient hashing schemes with essentially the same hashing strength of a completely random matrix but at a substantially lower cost in randomness, description size, and implementation complexity. The schemes are especially advantageous to hash large amounts of data.

We show cryptographic applications of these results to message authentication, where information is authenticated by encrypting the hash value under a (random or pseudorandom) one-time pad. We present specific efficient and practical constructions (e.g., based on linear feedback shift registers) that require short keys and short authentication tags, yet providing provable security.

These results include a full characterization of hash families that are secure for message authentication.

Document last modified on November 15, 1996