Proof that OTP is a perfect cipher

  • Thread starter Bipolarity
  • Start date
  • Tags
    Proof
In summary, the proof that the one-time pad (OTP) is a perfect cipher can be understood by examining the behavior of bits and the exclusive-or operation. The definition of a perfect cipher states that the probability of correctly guessing the message is equal to the probability of the original message. This is simplified to the equation P(m*=M | M \oplus k = c) = P(m*=M). By using the definition of the XOR operator, we can see that the event C = y is equivalent to the event K = x \oplus y, which is represented in the table provided. This shows that the OTP is a perfect cipher because the ciphertext is formed by the XOR operation of the key and the plaintext, making it impossible for
  • #1
Bipolarity
776
2
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
 
Physics news on Phys.org
  • #2
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
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
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
Thank you!

BiP
 

1. What is OTP and how does it work?

OTP, or one-time pad, is a type of encryption method that uses a random key to encrypt a message. This key is the same length as the message and is only used once, making it nearly impossible to crack.

2. What makes OTP a perfect cipher?

OTP is considered a perfect cipher because it meets all the criteria for a perfect encryption method. It has perfect secrecy, meaning that even if a hacker has unlimited computing power and time, they still cannot decipher the message without the key. It also eliminates patterns and repetition, making it impossible for frequency analysis to work.

3. Can OTP be cracked?

In theory, OTP cannot be cracked as long as the key is truly random and kept secret. However, it is important to note that the key must be kept secure and not reused. If the key is compromised or reused, then OTP can be cracked.

4. What are the limitations of using OTP?

One limitation of OTP is that it requires the distribution of a key that is the same length as the message. This can be difficult to do for large messages or for messages that need to be sent quickly. It also requires the key to be kept secure, which can be a challenge.

5. Are there any real-life examples of OTP being used?

OTP has been used historically by intelligence agencies for highly sensitive communications. It is also commonly used in some digital security systems, such as with two-factor authentication. However, due to its limitations and the advancement of other encryption methods, it is not commonly used in everyday communication.

Similar threads

  • Thermodynamics
Replies
4
Views
704
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
Replies
5
Views
375
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
3K
  • Linear and Abstract Algebra
Replies
3
Views
922
  • Mechanical Engineering
Replies
19
Views
2K
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
962
Replies
7
Views
1K
Replies
4
Views
1K
Back
Top