2007 - Exercises VI.
1.  Show that an adversary Eve can break the Rabin cryptosystem if she has access to the decryption machine (but not the key).
2.   (a) What is the probability that at least three students of the course IV054
have the same birthday?
(b) What is the probability that at least one student of the course IV054 have the same birthday as you?
(71 students attend IV054 course at this moment.)
3.  Suppose h : {0, l}2m —► {0, l}m is a strongly collision-free hash function. Let ti : {0, l}4m -»■ {0, l}m be defined as
h'{x) = h{h{xl)\\h{x2)),
where x\ is the first half of x and x2 is the second half of x. Prove that h! is strongly collision-free.
4.  None of the following definitions of secure encryption are correct (they do not express in sufficient detail what encryption is about). Find one or two errors in each of them.
Let Plaintexts, Keys, Ciphertexts be sets of strings of the same length over the same alphabet. Let e : Plaintexts x Keys —► Ciphertexts be an encryption function and d : Ciphertexts x Keys —► Plaintexts be a decryption function.
(a)  Let us denote Plaintexts = {P\,.., Pn}. Let {q{\i be a probability distribution on Plaintexts. For a given ciphertext C (which corresponds to a plaintext P) adversary knows that P = Pi with probability <&. Then (e,d) is a perfectly secure encryption scheme if {qí}í is uniform.
(b)  Let I(C, P) be mutual information between C = e[P, K) and P E Plaintexts for some key K. Then (e, d) is perfectly secure encryption scheme if I{C, P) = 0 for all C and P.
(c)  Let C = e[P, K) be a ciphertext for a plaintext P and a key K. Let A : Ciphertexts —► Plaintexts be an algorithm. Then (e,d) is perfectly secure encryption scheme if A{C) ^ P.
5.  Find all x E Z2o9 such that x2 = 80 mod 209. Explain (do not use brute force).
6.   (a) Let p, q be distinct primes. Suppose that x = y (mod p) and x = y (mod q).
Show that x = y (mod pq). (b) Let p, q be distinct primes and let k > 0 be an integer. Show that xfc(-p_1-)(-9_1-)+1 = x (mod pq).
7. Are the following functions negligible?  Explain your answer, you do not have to prove it.
(a)  l/x\
(b)  l/ffi
(c)  x~x
(d)   ýx-l
(e)   (Bonus)
l/f(x) where f(x) = the number of people eating hamburgers in fast food restaurants and x being the amount of money that McDonalds' spends on advertisements.