One-Time Pads

A simple cryptosystem offering perfect secrecy is known as a one-time pad.

Properties of a one-time pad

Although there are many different versions and ways of describing a one-time pad, they all have the same three essential properties:

• The number of possible keys is greater than or equal to the number of possible plaintexts: If the number of keys is less than the number of plaintexts, then guessing the key is easier than guessing the plaintext. This is why the cryptosystem doesn’t provide perfect secrecy. In most one-time pads, the number of possible keys is equal to the number of possible plaintexts.

• The key is selected uniformly at random from the keyspace: By uniformly, we mean each key is equally likely to be chosen. Suppose this is not the case. Recall that cryptosystem is being used to encrypt four-digit PINs. Suppose the PINs themselves are chosen uniformly at random, but the interceptor knows that certain keys are more likely to be chosen than others. In that case, the best strategy for the interceptor is to guess one of these more likely keys. Since this strategy will have a greater probability of success than guessing the plaintext, although the cryptosystem may still be pretty good, it will not offer perfect secrecy.

• A key should only be used once: This property is why a one-time pad is called ‘one-time.’ This doesn’t mean that after a key has been used, this key must never be used again. What it means is that each time a one-time pad is used, the current key should be discarded, and a new key should be selected uniformly at random from the keyspace. If by chance, the same key is selected on two different occasions, then that’s fine, since an attacker cannot predict when this might happen.

Note: These three properties alone don’t make one-time pads the preferred choice for everyone since there are cryptosystems that have these properties but do not have perfect secrecy. The property we normally aspire to have in a one-time pad is perfect secrecy. However, if a cryptosystem is a one-time pad, then it must have these three properties.