Hidden State

We say an autokey cipher has a hidden state if the previous ciphertext symbol does not fully determine the internal state of the cipher. Group autokey (GAK) ciphers can have a hidden state, in the form of a hidden subgroup. If there is no hidden state, then the cipher is in the space of group ciphertext-autokey (GCTAK) ciphers. The hidden subgroup has the restriction that it cannot be a normal subgroup, or contain a subgroup of the core of the group, or the cipher will reduce to something simpler. For this reason we generally only consider ciphers with irreducible hidden subgroups.

A practical example is that when working with a deck cipher, the top card of the deck (or at least the last card output as ciphertext) is visible, while the rest of the deck is in an unknown order, unless you know the exact cipher settings. The order of the rest of the deck is the hidden state, in this case the group for the $n$-card deck with all permutations is $S_n$ and the hidden subgroup is $S_{n-1}$.

Since not all hidden subgroups are possible for a given state group (without reducing to a simpler state group), figuring out exactly what group structures support a given ciphertext alphabet size for GAK ciphers is a fairly difficult problem. For example, there are only 6 groups that work for 83 CT symbols, with hidden subgroup sizes of 1, 2, 41, 82, 82!/2, and 82!. For other ciphertext alphabet sizes, we don't have an easy way to calculate the possibilities either, it just ended up being easy for 83 because 83 is prime.

I have enumerated all possible irreducible combinations of group and hidden subgroup for small groups (like 60 elements or fewer), and I will add them to this wiki at some point, along with all of their possible chaining graphs. This enumeration could be useful for solving this kind of cipher when small groups are used, even if it's not useful for the eyes.