# Skitel's noncommutative algebra based algorithm variation question

In Cryptanalysing variants of_Stickel's key agreement_scheme original attack against Stikel's key agreement and of some variants are presented.

The method is to find matrices $$X$$,$$Y$$ such that $$XA=AX$$, $$YB=BY$$ and $$U=XWY$$ and perform algebraic manipulations to get a system of linear equations that allows to recover the shared secret.

The original Stikel's key exchange is similar in concept to the ordinary Diffie-Hellman key agreement, in particular the operation to get the intermediate value of Alice or Bob the following expressions are used:

$$A,B,W\in GL(n,q)$$

$$AB\neq BA$$

$$U=A^lWB^m$$

From these done both by Alice and Bob a common secret can be agreed, $$l,m\in\mathbb{N}$$ are the private key of Alice, similarly for Bob.

The method to break this scheme is to find matrices $$X$$,$$Y$$ such that $$XA=AX$$, $$YB=BY$$ and $$U=XWY$$ and perform algebraic manipulations to get a system of linear equations that allows to recover the shared secret.

In particular $$X^{-1}$$ is used to get rid of the multivariate equations in $$U=XWY$$, not solvable by Gaussian elimination, so $$U=XWY$$ is transformed into $$X^{-1}U=WY$$, which is now solvable by Gaussian elimination as there's no product of matrices as unknowns.

The proposed variant is similar but changing the intermediate value, $$U$$ or $$V$$:

$$A,B,W\in GL(n,q)$$

$$AB\neq BA$$

$$U=A^lWB^m+A^pWB^q$$

From this equations a key agreement is done almost the same way, $$l,m,p,q\in \mathbb{N}$$ are the private key of Alice, similarly for Bob.

The question is there's no necessarily a $$U=XWY$$ for this construction. We can try to find $$U=X_1WY_1+X_2WY_2$$, but not as a system of linear equations as the inverse of $$X_1$$ trick does not work since the second term of the addition remains a product of two unknown matrices, so not solvable as a linear system.

So the question is if being $$U=A_1WB_1+A_2WB_2$$, how many, if any, solutions in the form $$U=XWY$$ there are and if any if it's cryptographycaly relevant or a side case which can be considered irrelevant. $$X$$, $$A_1$$ and $$A_2$$ commute pairwise the same as $$Y$$, $$B_1$$ and $$B_2$$.

First we must ensure $$U$$ is in $$GL(p,q)$$. Then just try to solve the overdetermined system of equations $$X_1A=AX_1$$, $$YB=BY$$ and $$X_1U=WY$$. If the system of equations is inconsistent there's no solution of the form $$U=XWY$$.