= Solution
A <cipher> has <perfect secrecy> when the <conditional probability> of every plaintext given a ciphertext equals its prior probability: $\Pr(M=m\mid C=c)=\Pr(M=m)$ whenever $\Pr(C=c)>0$. Equivalently, the plaintext and ciphertext are <independent random variables>.
Fix a ciphertext $c$ that can occur. Perfect secrecy requires every possible plaintext $m$ to remain possible after observing $c$. For a deterministic decryption rule, two different plaintexts producing $c$ require two different keys, so the key space has cardinality at least that of the message space.
In a <one-time pad>, the message and key belong to the same finite <additive group>, the key is <uniform distribution>[uniform] and independent of the message, and encryption is $C=M+K$. For every $m,c$ there is exactly one key $k=c-m$, so
$$
\Pr(C=c\mid M=m)=\Pr(K=c-m)=\frac1{|\mathcal K|},
$$
independent of $m$. <Bayes' theorem> then gives $\Pr(M=m\mid C=c)=\Pr(M=m)$, proving <perfect secrecy>.
Back to article page
