monoalphabetic substitution perfect secrecy
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.