5. (Bonus 20 points) We defined universal hash functions mapping {0,1....,-1} to {0,1.....k- 1} as follows. Let Ha 42.43.0 (81, 12, 13, 14) =( mod k. Then define H as follows: H = {H,42,43,44 | 21, 22, 23,44 {0,1.....k-1}}. () Prove the following claim. Claim 1. Let k be any prime number. For any kuo distinct tuples (11, 12, 13, 14) and (91, 92, 93, 94). Pr [H.,12.03.23 (21,22,23,2a) = H, 12,03,0, (01:42:98: 94)] where each is sampled from {0,1.....k-1} uniformly at random and independently. 1 The proof of this claim appears in the DPV book(towards the end of Chapter 1). You are allowed to look at the proof for this. However, you should understand and explain everything that you write here. (Note: k being prime is important for this claim. In the class, we used k = 256 for which the claim is simply incorrect!) (Bonus +10) Show that the claim is incorrect for k = 256