Proof of second half of Shannon's Theorem

2009-11-23T03:00:24Z

Prove the second half of Shannon's Theorem. That is, suppose that $\left(\mathcal{K},\mathcal{C},\mathcal{P},\mathcal{E},\mathcal{D}\right)$ is a cryptosystem with $\left|\mathcal{K}\right|=\left|\mathcal{P}\right|=\left|\mathcal{C}\right|$. Show that if

every key $K$ is used with equal probability $1/\left|\mathcal{K}\right|$;
for every $x\in\mathcal{P}$ and $y\in\mathcal{C}$ there is a unique key $K$ such that $e_K\left(x\right)=y$

then the cryptosystem provides perfect secrecy.

This is a question from an assignment I had for a coding and cryptology class in 2008 -- I have included my own answer below. I am just interested in other ways of proving this theorem.

First we consider the distribution $p_\mathcal{C}$. For the ciphertext $y\in\mathcal{C}$ (we are summing over every key $K$ that can lead to ciphertext $y$):

$p_\mathcal{C}\left(y\right)=\sum_{{K:y\in C\left(K\right)}}p_\mathcal{K}\left(K\right)p_\mathcal{P}\left(d_K\left(y\right)\right)=\sum_{K\in\mathcal{K}}p_\mathcal{C}\left(K\right)p_\mathcal{P}\left(d_K\left(y\right)\right)$

$p_\mathcal{C}\left(y\right)=\left(1/\left|\mathcal{K}\right|\right)\sum_{K\in\mathcal{K}}p_\mathcal{P}\left(d_K\left(y\right)\right)=1/\left|\mathcal{K}\right|$

Thus, as $p_\mathcal{P}\left(x|y\right)=p_\mathcal{P}\left(x\right)$, the cryptosystem provides perfect secrecy. QED.

Proof of second half of Shannon's Theorem - MathOverflow

Proof of second half of Shannon's Theorem