Perfect secrecy and the one-time pad theorem
In cryptography, perfect secrecy is the highest level of security an encryption scheme can achieve. It means that observing the ciphertext reveals absolutely no information about the original message. The one-time pad is a method that achieves this level of security, under specific conditions.
The one-time pad encryption technique involves a sender and a receiver who share a secret key. This key is a sequence of random bits, as long as the message itself. To encrypt a message, the sender performs a bitwise XOR operation between the message and the key. The receiver, to decrypt, applies the same key with another XOR operation to the ciphertext.
Mathematically, if M represents the message, K the key, and C the ciphertext, the encryption and decryption processes are:
\begin{aligned} C & = M \oplus K \\ M & = C \oplus K \end{aligned}
The security of the one-time pad relies on a theorem proven by Claude Shannon: perfect secrecy. This theorem states that if the key is truly random, as long as the message, and used only once, then the ciphertext is statistically independent of the plaintext.
This can be expressed mathematically as:
P(M = m \mid C = c) = P(M = m)
for all possible messages m and ciphertexts c. This equation signifies that the probability of any message m being the original message remains the same, regardless of knowing the ciphertext c. In essence, the ciphertext provides no information to an eavesdropper about the content of the message.
The proof of this theorem relies on the properties of conditional probability and the uniform distribution of the key. It demonstrates that because every possible ciphertext is equally likely for any given plaintext (due to the randomness of the key), observing a specific ciphertext does not change the probability of any plaintext.
For a one-time pad to actually provide perfect secrecy, three conditions on the key must be met:
- be genuinely random. Any predictability in the key compromises security,
- be at least as long as the message. If the key is shorter and reused, the system becomes vulnerable to attacks,
- be used only once. Reusing the key, even partially, can leak information when different messages are encrypted.
When these conditions are satisfied, the one-time pad offers unbreakable encryption, ensuring that my communication remains perfectly secret.
For more insights into this topic, you can find the details here.