Comments on definitions of universal hash families

In this short note, I am listing what I believe are the original sources of the most commonly used variations of universal hash families. Some of these definitions are often referenced incorrectly, or not referenced at all. Cryptography researchers have a long-standing and (I think) appropriate tradition of referencing the original sources of definitions of cryptographic primitives, and it is in this spirit that I am providing this list of references.

I have checked all the sources refenced below for accuracy. However, if there are any omissions and/or inaccuracies, I would appreciate being notified.

• Carter and Wegman first defined universal (U) hash families in 1979 in [CW].
• Wegman and Carter first defined strongly universal (SU) hash families in 1981 in [WC]. In this paper, they also introduced the concept of almost strongly universal hash families, but did not give a formal definition.
• Stinson first defined epsilon-almost universal (epsilon-AU) hash families and epsilon-almost strongly universal (epsilon-ASU) hash families at CRYPTO '91 in [S92] (the journal version of this paper is [S94]). These definitions first included the quantity epsilon as an explicit parameter of the schemes. For epsilon-AU hash families, epsilon denotes a collision probability; while for epsilon-ASU hash families, epsilon denotes a deception probability in the corresponding unconditionally secure MAC.
• Krawczyk first defined epsilon-almost xor universal (epsilon-AXU) hash families at CRYPTO '94 in [K94] (however, he used the term epsilon-otp-secure there). The more common terminology "epsilon-AXU" was first used by Rogaway at CRYPTO '95 in [R95].
• The generalization of epsilon-AXU hash families to arbitrary abelian groups was given by Stinson in 1996 [S96]; these are known as epsilon-almost Delta universal (epsilon-A Delta U) hash families.

References

[CW] J. L. Carter and M. N. Wegman,
Universal Classes of Hash Functions.
J. Computer and System Sciences 18 (1979), 143-154.

[K94] H. Krawczyk,
LFSR-Based Hashing and Authentication.
In ``Advances in Cryptology - CRYPTO '94'', Y. Desmedt, ed.
Lecture Notes in Computer Science 839 (1994), 129-139.

[R95] P. Rogaway,
Bucket Hashing and Its Application to Fast Message Authentication.
In ``Advances in Cryptology - CRYPTO '95'', D. Coppersmith, ed.
Lecture Notes in Computer Science 963 (1995), 29-42.

[S92] D. R. Stinson,
Universal Hashing and Authentication Codes.
In ``Advances in Cryptology - CRYPTO '91'', J. Feigenbaum, ed.
Lecture Notes in Computer Science 576 (1992), 74-85.

[S94] D. R. Stinson,
Universal Hashing and Authentication Codes.
Designs, Codes and Cryptography 4 (1994), 369-380.

[S96] D. R. Stinson,
On the connections between universal hashing, combinatorial designs and error-correcting codes.
Congressus Numerantium 114 (1996), 7-27.
(This papers is also published as Electronic Colloquium on Computational Complexity Report TR95-052, available from
http://www.eccc.uni-trier.de/eccc/ .)

[WC] M. N. Wegman and J. L. Carter,
New Hash Functions and their Use in Authentication and Set Equality.
J. Computer and System Sciences 22 (1981), 265-279.

Back to Doug Stinson's home page: click here.