# Perfectly secure shift cipher

Prove that if only one character is encrypted using a shift cipher, then the shift cipher is perfectly secure.

I want to show that $P(P=p | C=c)=P(P=p)$. But I don't know how to relate. Can anyone guide me?

Since you encrypt just a single letter, there are $26^2$ combinations of $p$ and $c$ where $c=E(p)$. This is because there are $26$ possible shift keys in the key space, an therefore each $p$ can be mapped to one of $26$ letters in the code space. Now, assuming that the key is distributed uniformly in the key space, each of those combinations of $(p,c)$ has a probability $\frac{1}{26^2}$. From base low we have: $$P(P=p\mid C=c) = \frac{P(P=p\text{ AND }C=c)}{P(C=c)}.$$ Now, $$P(P=p\text{ AND } C=c) = P(p,c) = \frac{1}{26^2},$$ and assuming uniform distribution $P(C=c) = 1/26$, you get $P(P=p|C=c) = \frac{1}{26} = P(P=p)$. QED

• What is your $p$ here? A single letter or a string of alphabets? – Idonknow Oct 7 '14 at 9:17
• Why can we assume that the distribution of ciphertext and plaintext are uniform? – Idonknow Oct 7 '14 at 9:48
• first, p is a single letter. for a string of letters, the shift cypher would not be a perfect cipher. Second, you are right: The proff may not assume that the distribution of plain text is uniform. – Evgeni Vaknin Apr 26 '15 at 19:25

To prove an encryption scheme to be perfectly secure, we need to prove: $$P[M=m|C=c]=P[M=m]$$ where $c$ is a cipher text and $m$ is a plain text.

From Bayes theorem, we have: $$P[M=m|C=c]=\frac{P[C=c|M=m] \cdot P[M=m]}{P[C=c]}$$

It is noteworthy that: $$P[C=c|M=m]=P[K=k]$$ where $K$ is the key space and $k$ is a particular key.

Now: $$P[C=c]=P[K=k]=\frac{1}{26}$$

Therefore, we have: $$P[M=m|C=c]=P[M=m]$$ $QED$.