Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

The 'family' means that there is actually an extra input, which is usually regarded as fixed.
For any finite field $\hspace{.03 in}F$, $\;\; H \: : \: F\times F^{\hspace{.02 in}2} \: \to \: F \;\;$ given by
$H\left(k,\hspace{-0.04 in}\langle x,\hspace{-0.03 in}y\rangle\hspace{-0.02 in}\right) \;\; = \;\; (k\hspace{-0.04 in}\cdot\hspace{-0.04 in}x)+y \;\;\;\;$ is a universal hash family.
It means to choose the first input at random.

share|improve this answer
    
Thanks to both NightCracker and Ricky Demer. The first answer is a bit expository, whereas the second one is precise and straight to the point. –  Govinda R Y Sep 12 '13 at 7:17
    
@GovindaRY the way to thank someone is to accept an answer. Pick the one you think best answers your question and click the "tick" button! –  rath Feb 10 at 17:57

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.

share|improve this answer
    
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? –  Paŭlo Ebermann Sep 11 '13 at 19:24
    
@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. –  orlp Sep 11 '13 at 19:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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