Proof that OTP is a perfect cipher

  • Thread starter Bipolarity
  • Start date
  • #1
775
1

Main Question or Discussion Point

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
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,124
1,301
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.
 
  • #3
775
1
The definition of a perfect cipher:

[tex] P(m*=M | E_{k}(M) = c) = P(m*=M) [/tex]

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

Simplifying, we get

[tex] P(m*=M | M \oplus k = c) = P(m*=M) [/tex]

[tex] \frac{P(m*=M \bigcap M \oplus k = c)}{P(M \oplus k = c)} = P(m*=M) [/tex]

I have trouble figuring out the probability of [itex]m*=M \bigcap M \oplus k = c [/itex] and [itex] M \oplus k = c[/itex].
 
  • #4
Stephen Tashi
Science Advisor
7,124
1,301
As I understand the question.

[itex] M [/itex] = the message bit
[itex] C [/itex] = the corresponding bit of the cypher text
[itex] K [/itex] = the corresponding bit of the key

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

The cypher bit is formed by [itex] C = M \oplus K [/itex]

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

For example, If [itex] M = 1 [/itex] then [itex] C = 1 [/itex] exactly when [itex] K = 1 \oplus 1 = 0 [/itex]
 
  • #5
775
1
Thank you!!!!

BiP
 

Related Threads on Proof that OTP is a perfect cipher

Replies
1
Views
2K
Replies
0
Views
984
Top