Let $M$ be a finite message space. Recall that a permutation on $M$ is a bijective function on $M^2$. Assume that permutations can be encoded/decoded and transferred efficiently. Prove that the following scheme has perfect secrecy:
- KeyGen : Sample a permutation $\pi$ from $M$ uniformly at random, from the space of all possible permutations, and return it as key.
- $Enc(m, \pi):$ Return $c = \pi(m)$
- $Dec(c, \pi):$ Return $\pi^{-1}(c)$
How to prove the above scheme following OTP perfect secrecy proof? I don't know the expression of KeyGen.
