Chaining Conflicts

When alphabet chaining fails to work for some ciphertext, we say it has a chaining conflict. There are several reasons for this, but they are generally from incorrect assumptions about the cipher (if not from clerical error like a typo in the transcription of the cipher). If the underlying plaintext for what are assumed to be isomorphs are not actually the same, then alphabet chaining can fail. Like for example if there are typos in the plaintext that are not drastic enough to break the visible isomorphism. Overextending isomorphs can also cause conflicts. Another more recent result is that group-based ciphers with a non-commutative group will cause chaining conflicts directly, and these kinds of conflicts can even be seen in the backbones of the isomorphs. This seems to be the kind of chaining conflict we see in the eyes, along with a few other quirks of the chaining graph structure which are exclusive to GAK ciphers (and perhaps generalizations of them).

However, there are several kinds of conflicts that present differently when trying to apply alphabet chaining to a cipher. Here are the main types:

• Commutativity Conflict

  • This type of conflict happens when looking at two pairs of isomorphs with transformations between them denoted as $a$ and $b$, where starting from some letter $A$, applying the changes in different orders give different results, as in $A \xrightarrow{a} B \xrightarrow{b} C, \hspace{1em} A \xrightarrow{b} D \xrightarrow{a} E, \hspace{1em} C \ne E$
  • This happens when the group elements corresponding to $a$ and $b$ do not commute with each other. This is not possible in CTAK because in a cyclic group, all elements are powers of some generator.
  • For other methods such as GCTAK and GAK, this isn't really a conflict, and is pretty normal, just means that the elements for the transformations between these isomorphs don't commute.

• Letter Placement Conflict

  • If you are trying to place an alphabet based on chains and find that the different letters would need to be placed at the same position, but the transformations do commute with each other, this could be considered a conflict, but is only a conflict if the group is cyclic. In non-cyclic groups, you can have cycles which contain different letters but still intersect in one or more shared letters.
  • To get around this issue, you need to expand your chained alphabet to a higher dimension. For example, instead of just a linear alphabet, create a 2D grid. This is primarily applicable to ciphers with non-prime ciphertext alphabet sizes.

• Order Conflict

  • If you build chains for a transformation between a pair of isomorphs, and it creates cycles of different sizes, this could be considered a conflict. This is not possible for CTAK or GCTAK, but is relatively normal for GAK. This can make it hard to know whether or not a nearly-complete cycle can have an inferred edge added to finish it.
  • A general strategy for reconciling these kinds of conflicts in a way that lets you place additional edges in the chaining graph is still a work in progress, we'd like help with this. However, for small well-understood groups, it was found that the geometry of the group structure determines the cycles of different sizes. For example, for GAK using a dihedral group with a reflection subgroup as the hidden subgroup, some of the order 2 elements create chaining graphs consisting of 2 fixed points (1-cycles) with the rest of the elements paired up into 2-cycles, and this can be geometrically interpreted with a reflection axis passing through the two fixed points.

• Arrow overlap conflict

  • Sometimes you can end up with two arrows in the chaining graph using different transformations, with the same start and end letter. Normally, this means you could merge the two arrow sets, but this kind of conflict happens if they cannot be merged because they act differently on other letters. This is impossible for CTAK and GCTAK, but relatively normal for GAK. This is only really a conflict if you try to merge the arrow sets and run into issues because it was an invalid assumption.
  • Depending on the complexity of the group and which hidden subgroup is chosen, and the relationship between the elements, it's possible for distinct elements of a group to show chaining graphs which share some edges in GAK. It's still research in progress when exactly this happens and how many shared edges are needed to say for certain that a pair of partial chaining graphs are actually instances of the same transformation and can be merged without issues. Initial results seem to indicate that it's related to the transitivity degree of the group's permutation action on the cosets of the hidden subgroup. In the worst case, with group $S_n$ and hidden subgroup $S_{n-1}$, actions can only be fully determined to be equal if all their edges are identical, because every permutation is possible. In simpler cases, such as dihedral groups, 2 edges being identical may be enough to say that two transformations are the same.

• True Conflict

  • There are two situations in the chaining graph which are actually real irreconcilable conflicts that indicate that something has gone horribly wrong in your assumptions about the chosen isomorphs. Looking at one particular transformation (color of arrow in the chaining graph), if a letter has two arrows coming out of it or two arrows coming into it from that same transformation, this is a direct conflict and is not possible for any group-based cipher, since it implies that the transformation between the two isomorphs is not a permutation (and not invertible).
  • The eyes do not show any true conflicts like this in any of their isomorphs, which is a good sign that the isomorphs do have an underlying permutation group for the transformations between them.
  • You will get this kind of conflict if you try to compare text which is not actually isomorphic. If the same known plaintext phrase is compared in different places and you get this kind of conflict, then the cipher method must not be perfectly isomorphic.