TOPICS
Search

Universal Hash Function

Let h:{0,1}^(l(n))×{0,1}^n->{0,1}^(m(n)) be efficiently computable by an algorithm (solving a P-problem). For fixed y in {0,1}^(l(n)), view h(x,y) as a function h_y(x) of x that maps (or hashes) n bits to m(n) bits. Let Y in _R{0,1}^(l(n)), then h is said to be a (pairwise independent) universal hash function if, for distinct x,x^' in {0,1}^n and for all a,a^' in {0,1}^(m(n)),

Pr_(Y)[(h_Y(x)=a) and (h_Y(x^')=a^')]=1/(2^(2m(n))),

i.e., h_Y maps all distinct x,x^' independently and uniformly.

These functions are easily constructible (Wegman and Carter 1981, Luby 1996).

See also

Hash Function

Explore with Wolfram|Alpha

References

Luby, M. Pseudorandomness and Cryptographic Applications. Princeton, NJ: Princeton University Press, 1996.Wegman, M. N. and Carter, J. L. "New Hash Functions and Their Use in Authentication and Set Equality." J. Comput. System Sci. 22, 265-279, 1981.

Referenced on Wolfram|Alpha

Universal Hash Function

Cite this as:

Weisstein, Eric W. "Universal Hash Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UniversalHashFunction.html

Subject classifications