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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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
-
$\begingroup$ What is your $p$ here? A single letter or a string of alphabets? $\endgroup$– IdonknowCommented Oct 7, 2014 at 9:17
-
$\begingroup$ Why can we assume that the distribution of ciphertext and plaintext are uniform? $\endgroup$– IdonknowCommented Oct 7, 2014 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$ Commented Apr 26, 2015 at 19:25
$\begingroup$
$\endgroup$
1
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$.
-
$\begingroup$ Why $P[C=c|M=m]=P[K=k]$? Explain this a little more please. $\endgroup$ Commented Jan 27, 2020 at 16:40