Skip to content

Chaining Conflict Rates

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

Some statistics on the rates of chaining conflicts for selected groups, mainly small ones where the rates can be exactly calculated, and groups that are potentially relevant to the eyes. Specifically the most common type of conflict, a failure for the transformations between pairs of isomorphs to be commutative.

Each pair of isomorphs has an associated group element giving the change in state between them (as the cumulative product of elements from the plaintext between the starts of the two isomorphs). I'm calling these "contexts." In the chaining graph, each distinct context has a different color of arrow. The conflicts happen when you look at 3 isomorphs and the context between 1 and 2 and the context between 2 and 3 don't commute with each other. Minor detail: Pairs of letters within an isomorph won't always have the same context (they always do for commutative groups), instead in general all the letter pairs in an isomorph pair are conjugates of each other (conjugating g by h in group theory meaning g^-1 * h * g), specifically conjugating by the sequence of plaintext from the start of the isomorph to that point.

To be able to observe a chaining conflict at all, first there needs to be enough letters present in the isomorphs to make a short chain that could conflict or not. Having the right repeated symbols among a set of three isomorphs for a conflict to be visible or not is a prerequisite, so the calculated rates here are assuming a given set of three isomorphs covers enough symbols for this condition to be met. Since contexts between isomorphs failing to commute is a direct cause of chaining conflicts, this chance is exactly the chance that two contexts fail to commute. You can calculate this probability directly by looking at all pairs of elements of the state group and counting how many pairs don't commute, divided by the size of the group. This isn't too difficult to calculate for small groups.

For a triplet of isomorphs with $n$ distinct symbols (remove any repeated letters) with a ciphertext alphabet length $m$, the chance of having the right repeated letters for visibility of a conflict or not, which requires a column (when the isomorphs are aligned) to have isomorphs 2 and 3 containing symbols from isomorph 1, is $1 - (1 - (n/m)^2)^n)$. If you have a long enough ciphertext with lots of repeats, this approaches 1. Really this just means that there needs to be enough repeated text in the messages that you can see these, like one long phrase repeated three times is usually enough.

Since this only happens with non-commutative groups, the probability of chaining conflicts for commutative groups is 0%. However, chaining conflicts can still appear based on incorrect assumptions of which sections of the text come from the same plaintext, due to overextended isomorphs, typos in the plaintext, or transcription errors (on the part of the solver or the puzzle designer).

Note that these rates only depend on the group structure, and not on any particular choice of hidden subgroup used, even though the number of CT symbols will be different. Larger CT alphabets just mean you'll need more/longer isomorphs to be able to see the right conditions for conflicts.

Assuming that condition is met, here are the chances that a random triplet of isomorphs causes a chaining conflict for some particular groups:

Group Order Chance
$D_6 \cong S_3$ 6 50%
$D_8$ 8 38%
$Q_8$ 8 38%
$D_{10}$ 10 60%
$D_{12}$ 12 50%
$A_4$ 12 67%
$D_{14}$ 14 64%
$D_{16}$ 16 56%
$D_{18}$ 18 67%
$D_{20}$ 20 60%
$AGL(1, 5)$ 20 75%
$C_7 \rtimes C_3$ 21 76%
$S_4$ 24 79%
$A_5$ 60 92%
$S_5$ 120 94%
$D_{26}$ 26 69%
$D_{52}$ 52 69%
$C_{26} \rtimes C_3$ 78 82%
$C_{26} \rtimes C_4$ 104 87%
$C_{26} \rtimes C_6$ 156 90%
$C_{26} \rtimes C_{12} \cong AGL(1, 26)$ 312 92%
$D_{166}$ 166 74%
$C_{83} \rtimes C_{41}$ 3403 98.73%
$C_{83} \rtimes C_{82} \cong AGL(1, 83)$ 6806 98.78%
$A_{83}$ 83!/2 ~100%
$S_{83}$ 83! ~100%
$C_7 \rtimes C_{12}$ 84 83%
$C_4 \times (C_7 \rtimes C_3)$ 84 76%
$C_7 \times (C_3 \rtimes C_4)$ 84 50%
$C_3 \times (C_7 \rtimes C_4)$ 84 64%
$C_{21} \rtimes C_4$ 84 71%
$C_2 \times (C_7 \rtimes C_6)$ 84 83%
$S_3 \times D_{14}$ 84 82%
$C_2 \times C_2 × (C_7 \rtimes C_3)$ 84 76%
$C_7 \times A_4$ 84 67%
$(C_{14} \times C_2) \rtimes C_3$ 84 86%
$C_6 \times D_{14}$ 84 64%
$C_{14} \times S_3$ 84 50%
$D_{84}$ 84 71%
$PSL(2, 7)$ 168 96.4%

Notation if you're not familiar with it:

37.5% seems to be the smallest chance among all non-commutative groups. In general the chances for even-sided polygons are lower than for odd-sided polygons, and it looks like doubling the sides for an odd polygon actually gives the same rate, e.g. a triangle and hexagon rotation and reflection symmetries, $D_6$ and $D_{12}$, have the same conflict rate, 50%.

These conflict rates might be useful for distinguishing the group in a random unknown group-based cipher with a lot of ciphertext, but it's more realistic to just use the chaining graph if you have that much ciphertext available.

So mainly this was an exploration to show that commutation conflicts aren't just a once-in-a-while thing, they're pretty much the norm, and with larger groups it just becomes more frequent... Which kind of makes me feel like we should be calling them something other than "conflicts," which makes it sound like something is broken, when it's really just how these groups operate and the "conflict" is the assumption that state changes between isomorphs commute with each other.

Clone this wiki locally