Group Autokey (GAK)

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.