Proof that non‐associativity breaks perfect isomorphism

(I'll fix the symbols on this later...)

Proof: Non-associative PT mapping elements lead to imperfect isomorphism A short summary of the result is that if Q is a loop and the set of PT mapping elements Im(p) is non-associative with elements of Q, then the resulting loop CTAK cipher is not perfectly isomorphic. For the specific condition, the requirement is that there exists some triplet of elements of Im(p), which we'll call q_1, q_2, and (q_1 q_2)^λ (the left inverse of their product), and there is some other element a in Q such that these don't commute: q_1 (q_2 a) ≠ (q_1 q_2) a. The most relevant case is when Im(p) is a non-associative subloop itself, in which case it will contain this left inverse of a product of non-associating elements.

Let L_q be the left multiplication map by q. Then the perfect isomorphism property can be restated as (L_(q_n) ... L_(q_2) . L_(q_1))(a) = a if and only if (L_(q_n) ... L_(q_2) . L_(q_1))(b) = b

Denote by F this composition of left multiplication maps, so that we can write this as F(a) = a if and only if F(b) = b

F does not act by multiplication of a single element like it would for a group, but as an action, it's still a permutation of the elements of the loop. Now we can see that this property is saying that the fixed points of F are either the whole loop (meaning a repeat in the ciphertext at some distance) or the empty set (meaning different ciphertext symbols at some distance for every initial state). If F fixes all points of Q, then it acts as the identity. Assume for the sake of contradiction that the PT mapping elements with the property above produce a cipher with perfect isomorphism. Since we have elements q_1, q_2, and (q_1 q_2)^λ in Im(p), we can look at the composition of their left multiplication maps: F = L_(q_1) . L_(q_2) . L_((q_1 q_2)^λ) F(x) = q_1 (q_2 ((q_1 q_2)^λ x))

Applying F to q_1 q_2 yields: F(q_1 q_2) = q_1 (q_2 ((q_1 q_2)^λ (q_1 q_2))) = q_1 q_2

So q_1 q_2 is clearly a fixed point of F. By perfect isomorphism, this means all elements of Q are fixed points of F, and F acts by the identity. So in terms of the composition we have L_(q_1) . L_(q_2) . L_((q_1 q_2)^λ) = L_e

Applying a right composition of L(q_1 q_2) to this (noting that L_(q^λ) = (L_q)^-1) gives L_(q_1) . L_(q_2) = L_(q_1 q_2)

Rewriting this as an operation on the element a shows q_1 (q_2 a) = (q_1 q_2) a

which is the definition of associativity, but we already assumed q_1, q_2, and a don't associate in the requirements, so this is a contradiction which implies that the assumption of perfect isomorphism must be false. It might be possible to extend this just a bit more by by allowing the elements q_1, q_2, and (q_1 q_2)^λ here to be compositions of elements of Im(p), but I'm not certain, because the composition of the multiplication maps can't be reduced to a left multiplication by a single element. But I think it's still the case that it ends up with imperfect isomorphism, so it should still be possible to prove in this case, it just might require a slightly different approach. It should also work when using more than two elements like this, just needs something that ends up at the identity while being non-associative. It should also be possible to extend this to loop autokey, but I'd have to think about it more. The analogy of the fixed point idea should be something like permuting the elements within each coset without swapping any cosets around...