Dihedral Group

The dihedral group $D_{2n}$ (sometimes written $D_n$, I mostly use the $2n$ convention because it has $2n$ elements) consists of the rotational and reflectional symmetries of a regular $n$-gon. In terms of permutations of a ciphertext alphabet of length $n$, this can be thought of as the group of rotations of the alphabet and of its reverse (or decimation by $n - 1$). As a group, the dihedral group $D_{2n}$ can be thought of as a semidirect product of the cyclic group $C_n$ and an order 2 reflection group $C_2$.

$D_{2n} \cong C_n \rtimes C_2$.

One physical implementation of group autokey (GAK) ciphers with this as the underlying group are mechanisms based on a cipher disk where each plaintext letter can rotate the disk by some particular amount (fixed for each plaintext alphabet letter) and can also optionally flip the disk over. The same symbols are written on both sides of the disk, but when the disk is flipped over, the following rotations appear to have the opposite effects. This lack of commutativity causes chaining conflicts. Using a dihedral group with GAK in this way corresponds to having the hidden subgroup be a reflection subgroup (order 2, consisting of the identity and one reflection), meaning there are two hidden states.

However, it has been shown that the eyes cannot be a dihedral cipher (with group $D_{166}$). Despite not fitting the eyes, dihedral group based GAK ciphers are a good candidate for development of an attack on ciphers with hidden states, since dihedral groups allow for making a system with only two hidden states with any ciphertext alphabet size, and it is the easiest type of case with two hidden states since the group is a semidirect product of a visible $C_n$ subgroup and the hidden $C_2$ subgroup. Having two hidden states means that for each visible ciphertext output, there are two possible states of the cipher that could have produced that output, and you can't tell which state the cipher is in at any given time unless you follow along with how the state updates from the beginning. At least that is how it appears. Maybe there is a way to determine the state using multiple characters or something. We haven't developed an attack for this yet, we could use some help. It seems likely we could use this proof to develop a known plaintext attack.