Learning Goal: I’m working on a cyber security question and need an explanation and answer to help me learn.
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(M), both σ and σ −1 are efficiently computable. Suppose P ⊂ S(M) is such that ∀x, y ∈ M, ∃σ ∈ P such that σ(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 σ ∈ P;
Encryption: m 7→ σ(m)
Decryption: c 7→ σ −1 (c)