3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is your $p$ here? A single letter or a string of alphabets? $\endgroup$ – Idonknow Oct 7 '14 at 9:17
  • $\begingroup$ Why can we assume that the distribution of ciphertext and plaintext are uniform? $\endgroup$ – Idonknow Oct 7 '14 at 9:48
  • $\begingroup$ 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. $\endgroup$ – Evgeni Vaknin Apr 26 '15 at 19:25
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.