Hash Family Example

I am reading my lecture and I found this definition:

Let be $F$ be a family of hash functions, that is, a parameterized set $$F=\{g_k:\{0,1\}^{*}\rightarrow\{0,1\}^{n}|k\in K\},$$ where $n\in \mathbb{N}$ and $K$ is a finite set.

Which could be an example of $F$?

-
Are you asking for real-world examples of such functions? – archie Jul 4 '13 at 1:43
Sounds like you want a keyed hash. A common choice is HMAC-SHA-2(k, m). With SHA-3 it's even easier since it's not subject to length extensions, so SHA-3(k||m) works. – CodesInChaos Jul 4 '13 at 6:11
@CodesInChaos Actually, the length extension property is not something which makes $F$ not a hash family, just one which is not useful for every goal. – Paŭlo Ebermann Jul 6 '13 at 10:45

A practical example with $n=128$ and $K=\{0,1\}^{32}$ would be the set $F$ of $2^{32}$ functions, one of which is MD5, obtained from the definition of MD5 by replacing the constant 0x67452301 with the integer which binary representation is $k\in K$. Each member of this family (each element of this set) is a function accepting a bitstring of any length, and producing a 128-bit bitstring.

Note: it is not immediately evident that this set really has $2^{32}$ elements: we could imagine that two different $k$ lead to the same function. It would be easy to disprove this experimentally, but that's another cup of tea if we extended $K$ to $\{0,1\}^{128}$ by considering the four initialization constants in MD5. It is common to sidestep this entirely, and consider without evidence that $F$ and $K$ have the same cardinality, which allows to assimilate a random element of $F$, and the element of $F$ corresponding to a random element of $K$.

Note: As for any hash family obtained using the Merkle–Damgård construction, the length-extension property makes it easy to recognize such hashes from a random oracle. This property allows to compute $g_k(M||X)$ with no knowledge of $k$, from knowledge of $g_k(M)$ and (the mere length of) $M$, for some $X$ chosen with knowledge of (the length of) $M$.

Note: Further, it turns out that MD5 is not computationally collision-resistant, and that extends to any member of this family $F$.

-

As explained in @fgrieu answer, you can always create such a function from a regular hash function by taking variations on the IVs or internal constant.

However, if you ask for a clean standardized hash function family, you will be hard pressed to find something satisfying.

If you are wondering why we encounter this dilemna, some additional explanation is required. Hash function families are used by crypto-theorist while practionners prefers hash function (single hash function not in a family and without a key).

The preference of the practionners is easy to understand, it is much more convenient to have this single hash function that everyone uses. No need to bother about the key that need to be used.

Theorists prefer hash function families because some of the properties that we ask of hash functions can be properly defined if you don't use a family. For example, defining a collision-free hash-function family is easy. The definition simply reads: *There exists no efficient adversary that given a key K outputs a collision for Hk.* With a single hash function, there is no such easy definition, because there exists an efficient adversary (in practice, the adversary is hard to find, but it exists nonetheless).

As far as I know, the only known alternative to using hash function families when interested by the theory of hash function is to use the random oracle model. EDIT: This last sentence is not completely true, I forgot to mention Rogaway's Human Ignorance approach.

-
There is a closely related question with answer there: cstheory.stackexchange.com/questions/16383/… – minar Jul 6 '13 at 17:42

$K \: = \: \{0,\hspace{-0.04 in}1\hspace{-0.01 in}\}^{2\cdot n^2}$

One can parse any $\:k\hspace{-0.03 in}\in\hspace{-0.02 in}K\:$ as $\:2\hspace{-0.04 in}\cdot\hspace{-0.04 in}n\:$ $n$-bit integers, and then build a compression function by
having the input indicate which of those integers to add and then reducing the sum modulo $2^{\hspace{.01 in}n}$.
That compression function can then be plugged into the Merkle-Damgård construction.

In Python, this would be given by

n = 256    # for example
initvector = ''.join(['0' for i in range(n)])
makefixedlength = '{0:0'+str(n)+'b}'
modulus = pow(2,n)

def g(k,m)
num = [int(k[n*i:n*(i+1)],2) for i in range(2*n)]
chainer = initvector
zpadded = m+'1'+''.join(['0' for i in range(-((len(m)+1)%(-n)))])