Proof of second half of Shannon's Theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T17:15:41Z http://mathoverflow.net/feeds/question/6519 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6519/proof-of-second-half-of-shannons-theorem Proof of second half of Shannon's Theorem lovek323 2009-11-23T03:00:24Z 2009-11-23T06:55:39Z <p>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</p> <ul> <li>every key $K$ is used with equal probability $1/\left|\mathcal{K}\right|$;</li> <li>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$</li> </ul> <p>then the cryptosystem provides perfect secrecy.</p> <p>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.</p> <p>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> <p>$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> <p>$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|$</p> <p>Thus, as $p_\mathcal{P}\left(x|y\right)=p_\mathcal{P}\left(x\right)$, the cryptosystem provides perfect secrecy. QED.</p>