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