Proof that GAK is uniquely reversible

Given a GAK cipher with group $G$, hidden subgroup $H$, plaintext alphabet $P$, ciphertext alphabet $C$, plaintext mapping function $p: P \to G$, and ciphertext mapping function $c: G \to C$ which partitions $G$ into right cosets of $H$, the state update and ciphertext output for plaintext letter $a_i \in P$ and state $g_i \in G$ are given by (assuming a left multiplication action):

$g_{i+1} = p(a_i) \circ g_i$

$c_i = c( p(a_i) \circ g_i )$

Choosing the plaintext mapping function $p$ such that there is at most one representative from each right coset will ensure unique reversibility. To prove this, the definition of cipher reversibility in this context is that given the current cipher state $g \in G$ and next ciphertext letter $b \in C$, there must be exactly one plaintext letter $a \in P$ which produces this ciphertext letter from the current state. Using the PT mapping function $p$ and the CT mapping function $c$, this means $c(p(a) g) = b$ for exactly one plaintext letter $a$.

By definition of the mapping function $c$ partitioning the group into right cosets of $H$ with different labels for each coset, $c(g_1) = c(g_2)$ if and only if $g_1$ and $g_2$ are in the same right coset, so $H g_1 = H g_2$. (This coset notation is a shorthand, $H g$ = { $h g : h \in H$ }.)

To prove by contradiction, suppose $c(p(a) g) = b$ and $c(p(a') g) = b$ for different plaintext letters $a \ne a' \in P$. Since these have the same value after applying the $c$ function, $p(a) g$ and $p(a') g$ must be in the same coset, so $H p(a) g = H p(a') g$. Right multiplying by $g^-1$ on both sides gives $H p(a) = H p(a')$, so $p(a)$ and $p(a')$ must also be in the same coset. But we required the PT mapping elements to be selected such that there was only one representative from each coset, and this contradicts that requirement, proving that this selection criterion ensures reversibility.

We can always select PT mapping elements in this way if the plaintext alphabet is not larger than the ciphertext alphabet, which is why we require that $|P| \le |C|$. Note that if $|P| = |C|$ the cipher will produce doubles, though.