Proof that OTP is a perfect cipher

[Bipolarity]

I'm trying to understand the proof that the OTP is a perfect cipher.
I tried to understand the proof shown in http://web.mit.edu/6.857/OldStuff/Fall97/lectures/lecture2.pdf but I don't understand the part C = y and K = (x XOR y).

Could someone assist me in understanding the proof?

Thanks!

BiP

 

[Stephen Tashi]

It looks like that's a statement about the behavior of bits and the exclusive-or operation. Write your question in the form of a question about arithmetic operations on single bits.

 

[Bipolarity]

The definition of a perfect cipher:

P(m*=M | E_{k}(M) = c) = P(m*=M)

where m* is the interceptor's guess at the message and M is the original plaintext message. k is the key used in the encryption, c is the ciphertext, and E is the encryption algorithm, in this case the XOR operator.

Simplifying, we get

P(m*=M | M \oplus k = c) = P(m*=M)

\frac{P(m*=M \bigcap M \oplus k = c)}{P(M \oplus k = c)} = P(m*=M)

I have trouble figuring out the probability of m*=M \bigcap M \oplus k = c and M \oplus k = c.

 

[Stephen Tashi]

As I understand the question.

M = the message bit
C = the corresponding bit of the cypher text
K = the corresponding bit of the key

Question: If M = x, why is the event C = y equivalent to the event K = x \oplus y?

The cypher bit is formed by C = M \oplus K

MKC
0 0 0
0 1 1
1 0 1
1 1 0

For example, If M = 1 then C = 1 exactly when K = 1 \oplus 1 = 0

 

[Bipolarity]

Thank you!

BiP