Re: Confirmation of Shannon's Mistake about Perfect Secrecy of One-time-pad

On Oct 23, 3:09 pm, wangyong <hell...@xxxxxxx> wrote:
Shannon misused Bayes' formula, similarly the above proof misused
Bayes' formula. From P(M = x)·P (K = (x⊕y)) = P(M = x) ·2-n, we can
see the condition that the ciphertext y is a fixed value is never
considered when computing P(M = xΛC = y). We can get that result by
reductio ad absurdum. Suppose for fixed y, if P (K = (x⊕y))=2-n (that
is used in the proof, but indeed it is wrong. It is used just to get
wrong conclusion), we can get P(M = x｜C = y)= 2-n because there is a
one-to-one correspondence between all the plaintexts and keys for the
fixed ciphertext in OTP. But it is obviously wrong, for the prior
probabilities of all plaintexts are seldom equally likely. So P(M =
x)·P (K = (x⊕y)) stand for the joint probability of x and y when y is
not fixed. But Shannon thought of the posterior probability as the
probability of plaintext when ciphertext had been intercepted, we can
see that there is a presupposition in P(M = x｜C = y) that y is fixed,
but in P(M = x), P (K = (x⊕y)) and P(C=y), y is not fixed, otherwise
we can get obviously wrong results. In such way, the Bayes's formula
was misused for the probability was not on the same presupposition and
the equation does not come into existence.
In OTP there are complex and crytic conditions that influence the
probability of plaintext, key and ciphertext, so it is essential to
cognize all the conditions and carefully use probability theory. The
proof did not realize the crytic condition that ciphertext was a fixed
value (even though unknown) rather than a random variable.

I suspect that a combination of typos and/or character set
incompatibilities have garbaged some of your equations. So, let me
have a guess at what you're saying.

Let's keep with the simple scenario where P(M=0) = p, P(M=1) = 1-p,
P(K=0) = 1/2, P(K=1) = 1/2, K and M independent. K=0 maps 0->0, 1->1,
and K=1 maps 0->1, 1->0. We intercept the encrypted message C=0.

I'm guessing that you are reasoning as follows: Given that C=0, there
is no longer an equal chance of K=0 and K=1. Because the proof uses
the fact that these probabilities are equal, the proof must be wrong.

In fact, the K-probabilities used in the calculation of the
conditional probabilities must be the *a priori* probabilities, which
are indeed equal, and the proof is sound.

You've obviously spent a while working with this symbolically, so you
might like to try a different approach to satisfy yourself. From your
affiliation I assume you are familiar with computer programming, so
try running a Monte Carlo-style simulation such as the following. You
will find that always M_equals_0 / total ~ p, and M_equals_1 / total ~
1 - p. This demonstrates that that probabilities of M=0 and M=1 are,
as expected, unaffected by the fact that C=0.

-----------------------------------------------------------

trials = 100000
p = 0.9

total = 0
M_equals_0 = 0
M_equals_1 = 0

For trial = 1 To trials

If Rnd < p Then M = 0 Else M = 1
If Rnd < 0.5 Then K = 0 Else K = 1
C = M Xor K

If C = 0 Then
total = total + 1
If M = 0 Then M_equals_0 = M_equals_0 + 1 Else M_equals_1 =
M_equals_1 + 1
End If

Next

Print M_equals_0 / total
Print M_equals_1 / total

-----------------------------------------------------------


.

Relevant Pages