Skip to content

Group Autokey (GAK)

Jump to bottom
Lymm edited this page Dec 6, 2025 · 6 revisions

Group autokey (GAK) ciphers are an extension of group ciphertext-autokey (GCTAK) ciphers which have an internal state given by some group with some hidden subgroup, giving it a hidden state. The number of ciphertext symbols is exactly given by the size of the state group divided by the size of the hidden subgroup. In the case of a trivial hidden subgroup, it reduces to a GCTAK cipher. The hidden subgroup also needs to be chosen in a particular way (in particular, the hidden subgroup must be non-normal and must not contain any subgroups in the core of the state group) or the cipher will partially or fully reduce to something simpler. For this reason we typically only look at irreducible choices of hidden subgroups.

Similar to GCTAK, all GAK ciphers consistently produce isomorphs when repeated plaintext sequences are used, so they have perfect isomorphism. They are able to avoid doubles with the correct choice of plaintext assignments to group elements. For reversibility, they are required to have each plaintext letter produce a distinct ciphertext output from an initial state of the identity element of the group. More precisely, each plaintext letter's assigned group element must be in a distinct coset of the hidden subgroup. Similar to CTAK and GCTAK, this kind of cipher produces an even frequency distribution over a long enough ciphertext.

For these reasons, GAK ciphers are a promising candidate for the eyes, and unlike the simpler ciphers in the isomorphic cipher hierarchy, not all types of GAK ciphers have been ruled out as options. There is an extension of GAK in the hierarchy which is still perfectly isomorphic, but it's not yet clear whether it will be necessary to resort to this more complex type of cipher, since GAK seems to cover all the necessary properties of the eyes already.

Among GAK ciphers with 83 ciphertext symbols, there are only a few (irreducible) options, and some of these have already been ruled out. See The Transitivity Restriction (6 Groups for 83) for more information.

A practical example implementation of GAK ciphers, which is also completely general, is a deck cipher. The reason deck ciphers are able to work as an implementation of any GAK cipher is because every group can be represented as a permutation group.

Precise definition of the method:

A GAK cipher (with the left multiplication convention) consists of the following information:

  • The plaintext alphabet $P$
  • The ciphertext alphabet $C$, which requires $|P| \leq |C|$
  • The state group $G$
  • A hidden subgroup $H < G$, where $H$ cannot be a normal subgroup
  • The plaintext mapping $p$, a function which assigns an element of the state group to each plaintext letter, $p: P \to G$
  • The ciphertext mapping $c$, a function which assigns each element of the state group to a ciphertext symbol, $c: G \to C$, such that $c$ is constant on the right cosets of $H$ in $G$ ($H g$), meaning $c(h_1 g) = c(h_2 g)$ for all $h_1$ and $h_2$ in H.
  • An initial state (optional, usually just the identity of the group)

The requirement of the ciphertext mapping to be constant on right cosets implies that the ciphertext alphabet is in correspondence with the right cosets, so the size of the ciphertext alphabet must be given by the formula:

$|C| = |G|/|H|$

The encipherment updates the state cumulatively. If the current state is $g_i$, and the current PT letter is $a_i$, then the state update to get the next state $g_{i+1}$ acting by left multiplication is:

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

And the CT output is:

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

(Equivalently, you can also act by right multiplication, and $c$ will need to be constant on left cosets instead.) Note that $g_0$ is the initial state.

For the cipher to be well-behaved, the PT mapping must be injective. The state update and CT output happens the same way as for GCTAK ciphers, except that for GCTAK ciphers, $c$ is bijective instead of just surjective. GCTAK is equivalent to using the trivial subgroup as the hidden subgroup. The plaintext alphabet must be smaller than the ciphertext alphabet in order to avoid doubles. Another requirement for the cipher to be reversible is that the PT mapping function $p$ cannot send more than one plaintext letter to the same coset. Choosing an element from the identity coset will cause doubles, so don't do that if you want to avoid doubles.

Choosing the PT and CT mapping functions in this way will ensure isomorphs, no doubles, and reversibility. Here are the proofs of these properties (which apply to GCTAK as well, since GCTAK is a special case of GAK):

Clone this wiki locally