8
$\begingroup$

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$?

$\endgroup$
5
$\begingroup$

The 'family' means that there is actually an extra input, which is usually regarded as fixed.

For any finite field $F, H : F\times F^{2} \to F$ given by $H\left(k,\langle x,y\rangle\right) = (k\cdot x)+y$ is a universal hash family.

It means to choose the first input at random.

$\endgroup$
0
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ For a block cipher, the usual "family parameter" is the key (this is why a block cipher is also a pseudo-random permutation family). Do you have an example for the parameter with actual hash functions? $\endgroup$ Sep 11 '13 at 19:24
  • 1
    $\begingroup$ @PaŭloEbermann BLAKE2 has a 8/16 byte personalization string, which you can see as a parameter selecting a hash function out of the family of BLAKE2 hash functions. But that's not it's only parameter - it also takes a salt and key. $\endgroup$
    – orlp
    Sep 11 '13 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.