Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof that OTP is a perfect cipher

  1. Aug 20, 2012 #1
    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?


  2. jcsd
  3. Aug 20, 2012 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
  4. Aug 20, 2012 #3
    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].
  5. Aug 20, 2012 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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]

    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]
  6. Aug 20, 2012 #5
    Thank you!!!!

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook