I'm wondering if there are other resources that cover Carter-Wegman style message authentication, besides the sources themselves.

Is there an online text or a book that covers their ideas? I'd prefer something that's very thorough, and less importantly, free. I'm just really trying to get a feel for their ideas and related works.

Wikipedia covers VMAC, which is an application of their ideas, here: http://en.wikipedia.org/wiki/VMAC


The original sources are linked through http://www.dblp.org/search/index.php#query=author:mark_n_wegman:&qp=H1.1000:W1.4:F1.4:F2.4:F3.4:F4.4

...and you can refine the search to just Wegman and Carter's works by clicking on Carter on the right side.

  • $\begingroup$ This should probably be migrated to Crypto.SE. $\endgroup$
    – D.W.
    Aug 25, 2012 at 18:14
  • $\begingroup$ Are you looking for something from the theory perspective (e.g., how to design or analyze a universal hash function)? Are you looking for something from the applied perspective (e.g., how to use Carter-Wegman hashing for message authentication in your application)? The answers will be very different in these two cases. $\endgroup$
    – D.W.
    Aug 25, 2012 at 18:15
  • $\begingroup$ @D.W.: I am slightly more interested in the theory, but I'm also very interested "the applied perspective" as well. So Really anything that covers this topic is of interest to me. I think that your reference to universal hashing in your answer may be a good place for me to start. $\endgroup$
    – Matt Groff
    Aug 25, 2012 at 19:13
  • $\begingroup$ cs.ut.ee/~lipmaa/crypto/link/mac contains some source from authors you mentioned hope it may help $\endgroup$ Aug 27, 2012 at 5:43

2 Answers 2


You didn't mention at what level you're hoping for, so I'll provide a few resources, and you can figure out which ones best meet your needs.

  • UMAC: Fast and secure message authentication. John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz and Phillip Rogaway, CRYPTO 1999. (This research paper describes UMAC, a fast Carter-Wegman style hash. It also gives a lot of good background on the topic.)

  • Wikipedia's entry on UMAC gives some background on universal hashing and its relevance to message authentication.

  • On fast and provably secure message authentication based on universal hashing, Victor Shoup, CRYPTO 1996. (This research paper gives some of the theory behind universal hashing. It might be a tough slog if you are not a theoretician.)

  • Stronger security bounds for Wegman-Carter-Shoup authenticators. Dan Bernstein, EUROCRYPT 2005. (Even more of the theory behind universal hashing. An even tougher slog, if you are not used to theoretical crypto, but good stuff if you are.)

  • If you want to learn some of the crypto-theory, here are some resources:

    • You could start with Chapter 7 of Bellare and Rogaway's lecture notes on modern cryptography, which provides an introduction to message authentication from a theoretical perspective. Read to the end of Section 7.4, then you can skip 7.5, 7.6, and 7.7, and jump straight to 7.8, which describes universal hashing -- but is unfortunately as yet incomplete.

    • You could read Katz and Lindell's Introduction to Modern Cryptography. Start with Chapter 1, then Chapter 4 (particularly 4.1-4.4). Unfortunately, while they have a good treatment of the theoretical foundations of message authentication, they don't cover universal hashing as a method of message authentication.

These days, Carter-Wegman-style message authentication is often mentioned under the name "universal hashing". That search term may help you find a lot more.


I found chapter 7 of the (still in progress) book "Graduate Course in Applied Cryptography" by Shoup and Boneh pretty useful as a thorough explanation of authentication based on universal hashing: https://crypto.stanford.edu/~dabo/cryptobook/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.