Reading the Crypto Classics: Carter and Wegman: “Universal Classes of Hash Functions”

Organizer: Shan Chen, TU Darmstadt, Cryptoplexity Group

Abstract

This talk is the final one in the seminar series “Reading the Crypto Classics” for the very special winter term 2022. The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper/talk Carter and Wegman: “Universal Classes of Hash Functions” (JCSS 1979) with the following abstract (extracted from summary):

“This paper gives an input independent average linear time algorithm for storage and retrieval on keys. The algorithm makes a random choice of hash function from a suitable class of hash functions. Given any sequence of inputs the expected time (averaging over all functions in the class) to store and retrieve elements is linear in the length of the sequence. The number of references to the data base required by the algorithm for any input is extremely close to the theoretical minimum for any possible hash function with randomly distributed inputs. We present three suitable classes of hash functions which also can be evaluated rapidly. The ability to analyze the cost of storage and retrieval without worrying about the distribution of the input allows as corollaries improvements on the bounds of several algorithms.”

Further information about the virtual format

For participation the following meeting link is required:
https://tu-darmstadt.zoom.us/j/86701175893?pwd=cVRiRTB3azVVMDZpOVFKTmczT0U1Zz09

More information

CROSSING Wiki