Many definitions related to universal hashing mention the term "a family of hash functions, say $H$". What does this 'family' mean exactly? A numerical example would be appreciated. Also, what does it mean to choose a hash function h at random from a hash family $H$?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
In general, having a family of functions means that you have a function definition with a small detail, change, parameter or other tweak that can vary from function to function.
An (insecure) example would be if you'd parametrize the S-box in AES. Then you have a family of functions, and you select a particular member of that family by specifying the S-box. If you'd specify the S-box to be equal to the AES S-box you'd have AES.
Selecting a member of a function family at random means that you select the parameter at random. An example would be to randomly generate the S-box byte by byte.
The 'family' means that there is actually an extra input, which is usually regarded as fixed.