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.