1.2: One-Time Pad

Now with a clear definition of encryption syntax, we can give the specifics of one-time pad (OTP)encryption. The idea of one-time pad had historically been attributed to Gilbert Vernam, a telegraph engineer who patented the scheme in 1919. In fact, one-time pad is sometimes called “Vernam’s cipher.” However, an earlier description of one-time pad was recently discovered in an 1882 text on telegraph encryption by banker Frank Miller.

Construction \(\PageIndex{1}\) : One-Time Pad:

\[K={\{0,1\}}^{\lambda}\space\space\space\space\space \underline{\text{KeyGen:}}\space\space\space\space\space \underline{\text{Enc(}k,m):}\space\space\space\space\space \underline{\text{Dec(}k,c):}\\M={\{0,1\}}^{\lambda}\space\space\space\space\space \space k\leftarrow K\space\space\space\space\space\space\text{return}\space k\oplus m \space\space\space\space\space\space \text{return}k\oplus c\nonumber \] \(C={\{0,1\}}^{\lambda}\space\space\space\space\space \space \text{return}\space k\)

Here are a few observations about one-time pad to keep in mind:

• Enc and Dec are essentially the same algorithm. This results in some small level of convenience when implementing one-time pad.
• One-time pad keys, plaintexts, and ciphertexts are all the same length. The encryption schemes we will see later in the course will not have this property.
• Although our encryption syntax allows the Enc algorithm to be randomized, one-time pad does not take advantage of this possibility and has a deterministic Enc algorithm.
• According to this definition, one-time pad keys must be chosen uniformly from the set of λ-bit strings.

The correctness property of one-time pad follows from the properties of XOR listed in Section 0. For all \(k, m\in\{0,1\}^{\lambda}\), we have:

\[\text{Dec(}k, \text{Enc(}k,m))=\text{Dec}(k, k\oplus m)\\\space\space\space \space\space\space\space\space\space\space\space\space\space\space\space \space\space\space\space\space\space \space\space\space\space\space\space =k\oplus(k\oplus m)\\\space\space\space\space\space\space\space\space\space\space\space\space \space\space\space\space\space\space\space\space\space\space\space\space =(k\oplus k)\oplus m\\\space\space\space\space\space\space \space\space\space\space\space\space\space\space\space\space\space\space =0^{\lambda}\oplus m\\\space\space\space\space\space\space \space\space\space\space =m\nonumber\]

Example \(\PageIndex{1}\):

Consider using OTP encryption to encrypt the 20-bit plaintext m under the 20-bit key \(k\) givenbelow:

The result is ciphertext \(c\). Decrypting \(c\) using the same key \(k\) results in the original \(m\):

References

1. Steven M. Bellovin: “Frank Miller: Inventor of the One-Time Pad.” Cryptologia 35 (3), 2011.