One-time pad

From CRYPTUTOR

One-time pad encryption is a very simple private-key encryption scheme that achieves (one-time) perfect secrecy.

Definition

In one-time pad, the keys, messages, and ciphertexts are $n$ -bit strings, where $n$ is the security parameter. The encryption scheme is defined by the following algorithms:

Key generation: Choose an $n$ -bit string $K$ , uniformly at random.
Encryption: $\mathsf{Enc}_K(m) = K \oplus m$
Decryption: $\mathsf{Dec}_K(c) = K \oplus c$

Here, " $\oplus$ " denotes the bitwise exclusive-or (XOR) operator. It is easy to see that $\mathsf{Dec}_K(\mathsf{Enc}_K(m)) = m$ .

It is not hard to show that for each message $m$ , the distribution $\{\mathsf{Enc}_K(m)\}_{K \gets \mathsf{KeyGen}}$ is the uniform distribution over $n$ -bit strings, and thus the scheme has perfect secrecy.

[edit]

Generalization

We can modify one-time pad to get a perfecly secret encryption scheme in any group. In the above description, replace the set of $n$ -bit strings with any group $\mathcal{G}$ . Let encryption be the group operation with the key (a randomly chosen group element), and decryption be the group operation with its inverse. In the group induced by the XOR operation on strings, every element is its own inverse.