The One-Time-Pad generalized to groups

We recap the usual OTP with encryption in $\{0, 1\}^n$ being $m \oplus K$ and note how its slogan “every ciphertext can come from any plaintext” justifying its security is just a consequence of the group structure in $\{0, 1\}^n$. We then formulate the more general OTP over groups.

The usual OTP

The One-Time-Pad is an uncrackable albeit idealistic encryption scheme. It goes as follows:

Definition (One-Time-Pad [OTP]): Define $\Pi := (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$:

• Gen: sample $K \in \{0,1\}^n$
• Enc: define $\mathrm{Enc}(K, m) := m \oplus K$
• Dec: define $\mathrm{Dec}(K, c) := c \oplus K$

It is uncrackable in the sense that it achieves indistinguishable encryption in the presence of an eavesdropper in the information-theoretic sense¹: $$\mathrm{Pr}(\mathrm{EAVExp}_{\mathcal{A}, \Pi}(n) = 1) = \frac{1}{2}$$

Intuition behind the OTP’s security

When you first see this security result, it may be a bit surprising and counter-intuitive. For example, it may happen that $K = 0^n$ is chosen in the key generation algorithm implying that $\mathrm{Enc}$ is a no-op. It just returns the message it plain. To reconcile this with intuition, note that *every* ciphertext in $\{0,1\}^n$ can result from any message in $\{0,1\}^n$. For instance, take $n = 4$, $K = 0000$, and $m = 0110$. Then, encryption will give you the ciphertext $c = m = 0110$. If the adversary does not know our key $K$, there is no way they can deduce from which message the ciphertext resulted. It could have indeed been $0110$ (with $K = 0000$), or $1111$ (with $K = 1001$), or any other 4-bit string.

Generalizing the “everything can result from anything” property

Is this property of “everything can result from anything” intrinsic to strings and xor operations? Fortunately, having taken math lectures for my minor helped me quickly answering this question: it’s a property of groups. Let $G$ be a group with “everything” $a \in G$ and “anything” $b \in G$. Then $ab^{-1}$ is the action going from $b$ to $a$, namely $(ab^{-1}) \cdot b = a$.² And indeed, $(\{0,1\}^n, \oplus)$ forms a group.

Let’s formulate the OTP over groups:

Definition (One-Time-Pad over Group [G-OTP]): Let $G$ be a group where multiplication and inversion can be efficiently computed and from which group elements can be sampled from uniformly at random in an efficient way.

Define $\Pi’ := (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$:

• Gen: sample $K \in G$
• Enc: define $\mathrm{Enc}(K, m) := m \circ K$ for $m \in G$
• Dec: define $\mathrm{Dec}(K, c) := c \circ K^{-1}$

You see that we needed some conditions on the group which were implicit in the choice of $\{0, 1\}^n$ before. The proof of indistinguishability of the G-OTP is completely analogous to the one of the usual OTP.