Notes on One-Time Pad Encryption

Introduction

• Problem: How to design a cipher that hides Alice's fingerprint
• Solution: Use randomness to stop information leaks

Concept of One-Time Pad

• Alice generates a long list of random shifts using a 26-sided die.
• This list is shared with Bob instead of a code word.
• The list of random shifts must be as long as the message to avoid repetition.

Encryption Process

1. Message Encryption
   • Alice encrypts her message using the random shifts.
2. Message Decryption
   • Bob decrypts the message using the same list of random shifts.

Properties of Encrypted Message

1. Non-Repetitive Patterns
   • The shifts do not fall into a repetitive pattern.
2. Uniform Frequency Distribution
   • The encrypted message has no frequency differential, making it hard to break.

Strength of One-Time Pad

• Emerged towards the end of the 19th century.
• Considered the strongest method of encryption.

Combinatorial Explosion

• Caesar Cipher:

  • Shifts every letter by the same shift (1 to 26 possibilities).
  • For example, Alice’s name has 26 possible encryptions.

• One-Time Pad:

  • Each letter shifted by a different number between 1 and 26.
  • Total number of possible encryptions: 26^5, which is almost 12 million.

Visualization of Possibilities

• Imagine stacking every possible five-letter encryption on top of each other.
• This stack would be over one kilometer high.

Conclusion

• When Alice encrypts using the one-time pad, it is akin to randomly selecting one from this enormous stack of possibilities.
• For Eve, every encrypted word is equally likely to correspond to any word in this stack, demonstrating perfect secrecy.