monoalphabetic substitution perfect secrecy

I have this question that I'm trying to answer:

Consider a monoalphabetic substitution cipher applied to plaintexts consisting of just a single letter. That is, $$M = \{0, 1, . . . , 25\}$$ The keyspace $K$ is the set of all permutations of $M$. (As usual, we identify the letter $A, . . . , Z$ with this set of integers.) Show that this is perfectly secret.

I understand that to show perfect secrecy it suffices to show that $|K|\ge |M|$. I'm just not understanding how to answer this question. Would it make sense to say $K = \{0, 1, ..., 25\}\Rightarrow |K|\ge |M|$?

• The key space being at least as big as the message space is only a necessary condition for perfect secrecy, but not a sufficient one. For example, AES128 will not offer perfect secrecy when encrypting a single block. – CodesInChaos Feb 9 '17 at 8:16
• @CodesInChaos so then what do I have to show in order to perform this task? – R. Kelly Feb 9 '17 at 8:19

1 Answer

IF $K$ is randomly chosen (and well distributed over the key space with size 26! - the total number of possible permutations) then each $C$ (ciphertext letter) is also equally likely. An attacker may choose any $K$ but it is impossible to gain any advantage by that; each message $M$ is still as likely as before.

Basically this scheme is a one-time-pad using a per-character permutation rather than XOR as often used.

As indicated by the first IF, what's missing is the requirement that the choice of $K$ is perfectly random. Generally we try and proof ciphers correct by looking at the set $\operatorname{Gen}, \operatorname{E}, \operatorname{D}$. The $\operatorname{Gen}$ is missing from the question.

• I'm not sure if you already used $Pr$ (probability) notations for this question, so I tried to refrain from using those. – Maarten Bodewes Feb 9 '17 at 12:39
• The keyspace is defined as the set of all permutations, so it's $26!$ possible keys. It's not just modular addition instead of XOR. In this case, it should be included that for all messages $m$ and ciphertexts $c$, $25!$ of those permutations map $m$ to $c$, and for a random permutation this has the probability $25! / 26! = 1/26$. For any fixed $c$, each $m$ can be the preimage exactly with probability $1/26$. – tylo Feb 9 '17 at 13:14
• Ok, I'll try and adjust he answer accordingly (traveling right now). The fact remains of course that the key must be chosen at random from the possibe keys though. – Maarten Bodewes Feb 9 '17 at 13:56
• Changed answer, a more formal answer is probably asked for though; if somebody can post that I'd happily vote up. – Maarten Bodewes Feb 10 '17 at 11:49