Prove that if an encryption scheme has |.K| < |.M| then it cannot satisfy one- time secrecy. Try to structure your proof as an explicit attack on such a scheme (i.e., a distinguisher against the appropriate libraries).

In one-time pad, Enc is a deterministic function but for full credit, you should prove the statement even if Enc is randomized. However, you may assume that Dec is deterministic.

Hint: The definition of interchangeabilitiy doesnt care about the running time of the dis- tinguisher/calling program. So even an exhaustive brute-force attack would be valid.

Let denote an encryption scheme and define 2 to be the following encrypt-twice scheme:

K = (.K)2 M = .M

C = .C

KeyGen: k1 .K

k2 .K return (k1,k2)

Enc((k1,k2),m): c1 := .Enc(k1,m) c2 := .Enc(k2,m) return (c1,c2)

Dec((k1,k2),(c1,c2)): m1 := .Dec(k1,c1) m2 := .Dec(k2,c2) if m1 m2 return err return m1

Prove that if satisfies one-time secrecy, then so does 2.