Assume that you have N bins and M balls, and you are randomly placing each of the balls in some bin (several balls might be placed in the same bin. Let pN,M denote the probability of a collision, i.e, the probability that at least two balls end up in the same bin. a) Prove that pN,M 1 e M(M1) 2N Hint: Use the following inequality: For any x R with 0 x 1 : 1 x e x . b) Let H() : {0, 1} {0, 1} n be a hash function that behaves as (i.e., is perfectly indistinguishable from) a random oracle. Prove that if an adversary tries 2 n+1 values then with probability greater than 1/2 he will find a collision in H. Hint: Use the following inequality: For any x R with 0 x 1 : 1e x (1e 1 )x

The Birthday Bound Assume that you have N bins and M balls, and you are randomly placing each of the several balls might probability of a collision, .e, the probability that at least two balls end up in the same bin. a) Prove that Hint: Use the following inequality: For any x R with 0 s 1: 1- e b) Let H(-) : {0,1)* {0,1)" be a hash function that behaves as (i.e., is perfectly in- distinguishable from) a random oracle. Prove that if an adversary tries v2"+I values then with probability greater than 1/2 he will find a collision in H Hint: Use the following inequality: For anyzERwith0 z 1: 1-e--(1-e-1)2