Let a M be a finite set of messages, and let S(M) denote the set of all permutations of M (all…
Let a M be a finite set of messages, and let S(M) denote the set of all permutations of M (all bijective functions f : M ? M). We’ll assume that if given a description of s ? S(M), both s and s -1 are efficiently computable. Suppose P ? S(M) is such that ?x, y ? M, ?s ? P such that s(x) = y.
(a) Show that |P| = |M|. (This is easy, but makes sure you’ve parsed the definition.)
(b) Show that if |P| = |M|, then the following encryption scheme is perfectly secure, provided you only use it once: 1 Key generation: select a random s ? P; Encryption: m 7? s(m) Decryption: c 7? s -1 (c)
(c) Show that the above is false if |M| < |P| < 2|M|.
(d) Observe that for any finite group G and any g ? G, the map x 7? gx is a permutation of G. By viewing G itself as a set of permutations of G in this way, show that the above property is satisfied (with M = P = G). (e) The traditional xor one time pad is a special case of the above. What is the finite group in this case?