Let H be a class of hash functions in which each hash function h H maps

Let H be a class of hash functions in which each hash function h ε H maps the universe U of keys to {0, 1, . . . , m — 1}. We say that H is k-universal if, for every fixed sequence of k distinct keys 〈x⁽¹⁾, x⁽²⁾, . . . , x^(k)〉 and for any h chosen at random from H, the sequence 〈h(x⁽¹⁾), h(x⁽²⁾), . . . ,h(x^(k))〉 is equally likely to be any of the m_k sequences of length k with elements drawn from {0, 1, . . . ,m — 1}.

a. Show that if the family H of hash functions is 2-universal, then it is universal.

b.

c.

d. Suppose that Alice and Bob secretly agree on a hash function h from a 2-universal family H of hash functions. Each h E H maps from a universe of keys U to Zp, where p is prime. Later, Alice sends a message m to Bob over the Internet, where me U. She authenticates this message to Bob by also sending an authentication tag t = h (m), and Bob checks that the pair (m, t) he receives indeed satisfies t = h(m). Suppose that an adversary intercepts (m' , t') en route and tries to fool Bob by replacing the pair (m, t) with a different pair (m', t'). Argue that the probability that the adversary succeeds in fooling Bob into accepting (m', t') is at most 1/p, no matter how much computing power the adversary has, and even if the adversary knows the family of hash functions used.

Transcribed Image Text:

(п-1 haь (x) —D (—а,х, + b) mod p j=0