Let H be a class of hash functions in which each hash function h H maps the universe U of keys to {0, 1,

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.

(-1 ha (x) D (,, + b) mod p j=0