Universal hashing and geometric codes (Q1358661): Difference between revisions

A universal class of hash functions is, grosso modo, a collection of hash functions such that a random choice of a function in the set yields a low probability that any two distinct inputs will collide. The concept is due to Carter and Wegman, and has numerous applications. (See the introduction to [\textit{D. R. Stinson}, Combinatorial techniques for universal hashing, J. Comput. Syst. Sci. 48, 337-346 (1994; Zbl 0806.68084)]). In the present paper it is shown that the theory of a certain type of universal class of hash functions is equivalent to the theory of error-correcting codes, and that there are precise conditions on algebraic curves for associated algebraic-geometric codes to give good universal classes. Universal classes better than any previously known are derived from codes based on Artin-Schreier, Hermitian, and Suzuki curves. It is interesting that the codes useful in this theory are quite different from the codes useful in communications.