Perfect Secrecy for Shift Cipher

Question

I've read the definition of perfect secrecy as the following:

A cryptosystem has perfect secrecy if $\Pr(x | y) = \Pr(x)$, for all $x \in P$ and $y \in C$, where $P,C$ are respectively the set of plaintexts and ciphertexts.

Now suppose there are 26 keys in the Shift Cipher (SC) with probability 1/26. Then for any plaintext with probability distribution, SC has perfect secrecy.

The proof starts with:

$$\Pr(y) = \sum_{k \in \mathbb{Z}_{26}} \Pr(k)\Pr\left(x = d_k(y)\right)$$

I didn't comprehend this part (the probability distr. on $C$), and the way it's calculated.

obs.: the encryption rule for shift cipher is $e_k(x) = (x+k) \text{ mod 26} (x \in \mathbb{Z_{26}})$.

Also note that $K$ is the set of keys.

Answer 1

We will prove that $\Pr[x |y] = \Pr[x]$, first notice that, since, for each element of $P$, we always have an element of $C$, under a key, $\Pr\left(x = d_k(y)\right) = 1$, so:

$$\Pr(y) = \sum_{k \in \mathbb{Z}_{26}} \Pr(k)\Pr\left(x = d_k(y)\right) = \sum_{k \in \mathbb{Z}_{26}} \Pr(k) $$

Now, the sum stands for the union of all associations of one key and a decryption.

But, since $e_k(x) = (x+ K) = y \mod 26$, we conclude that $\Pr\left(x = d_k(y)\right) = \Pr (y-K) = 1$. It's clear that $\Pr(k) = 1/26$, so $\Pr(y) = 1/26$.

Now, $\Pr[y|x] = \Pr[K] = 1/26$, because given $x$, $y$ is unique (uniquely determined via the $K$). Now by Bayes' Theorem we know:

$$\Pr[x|y] = \frac{\Pr[x]\Pr[y|x]}{\Pr[y]} = \frac{\Pr[x]\cdot 1/26}{1/26} = \Pr[x]$$

and this concludes the fact that Shift Cipher brings Perfect Secrecy.