University of Waterloo
The technique of universal hashing, introduced in 1979 by Carter and Wegman, has become an essential tool in many areas of computer science, including derandomization, pseudorandom number generation, and data authentication, to mention three specific applications. It has been observed that universal hash families are very closely related to combinatorial structures such as orthogonal arrays and error-correcting codes. However, the connection with these combinatorial structures and universal hash families often has not been exploited to its full potential.
In this talk, we review some applications of universal hashing, paying particular attention to the so-called "leftover hash lemma". We provide a simple combinatorial proof of this result, and survey several consequences of this lemma, including the construction of extractors and dispersers (which are used in derandomization of probabilistic algorithms) and quasirandom number generators (which are used in cryptography). Finally, we discuss how codes and orthogonal arrays can be used to provide simple constructions of these objects for various parameter situations of interest.
Please join us for refreshments before the lecture at 2:30p.m. in room 203 RSC.
[ Fall 2000/A>]