Homework 3
Out:Sep.10, Due:Sep.17
1. When using the one-time pad with the key k=0e, we have Enck(m)=k m=m and the message is sent in the clear!It has therefore been suggested to modify the one-time pad by only encrypting with k≠0(i.e.,to have Gen choose k uniformly from the set of nonzero keys of length e).Is this modified scheme still perfectly secret?Explain.
2. Let M={0,1}≤e be the message space containing all nonempty binary strings of length at most l.
(a)Consider the encryption scheme in which Gen chooses a uniform key from K={0,1}°, and Enck(m)outputs kim| m,where kt denotes the first t bits of k.Show that this scheme is not perfectly secret for message space M.
(b)Design a perfectly secret encryption scheme for message space M.
3. (For this problem we will give the definition of a PRG on Monday,but you can start before that because the definition is in the book.)
Define the function G as G(s)=s||s(where“”denotes string concatenation).State which parts of the PRG definition G satisfies(e.g.deterministic polynomial-time,expansion,pseu- dorandomness),and then describe and analyze an attack showing that G is not a pseudoran- dom generator.That is,give a distinguisher,and analyze the probabilites associated with each distribution.