# Perfect Secrecy for Shift Cipher

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.

• Any $c = x + k$, so probability of selecting $k$ times probability of there is $x$ decryption of $y$ under the key. In this case, second is always 1. And sum all. Commented Dec 26, 2021 at 17:22
• Why second is always 1? Commented Dec 26, 2021 at 17:29
• For every plaintext there is always a ciphertext under any key, and the reverse is also true. Commented Dec 26, 2021 at 17:30
• If you read the answer properly you need to see that; Shift Cipher (SC) can only attain perfect secrecy if it is restricted to one letter encryption. So one needs to mention this; let $SC'$ be the modified $SC$ such that for a random key it only encrypts one character. In the end, this is what One-Time-Pad if you continue to use another random key per character. Commented Dec 27, 2021 at 11:39

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.