General algebraic cryptographic key exchange scheme and its cryptanalysis

We show that many known schemes of the cryptographic key public exchange protocols in algebraic cryptography using two-sided multiplications are the special cases of a general scheme of this type. In most cases, such schemes are built on the platforms that are subsets of some linear spaces. They have been repeatedly compromised by the linear decomposition method introduced by the first author. The method allows to compute the exchanged keys without computing any private data and, consequently, without solving the hard algorithmic problems on which the assumptions are based. Here, we show that this method can be successfully applied to the following general scheme and, thus, is a universal one. The general scheme proceeds as follows. Let $G$ be an algebraic system with the associative multiplication, for example, a group chosen as the platform. We assume that $G$ is a subset of a finitely dimensional linear space. First, some public elements $g_1,\dots,g_k\in G$ are taken. Then the correspondents, Alice and Bob, sequentially publicise the elements of the form $\varphi_{a,b}(f)$ for some $a,b\in G$, where $\varphi_{a,b}(f)=afb$, $f\in G$ and $f$ is a given or previously built element. The exchanged key has the form
\begin{equation*} K=\varphi_{a_l, b_l}(\varphi_{a_{l-1},b_{l-1}}(\dots(\varphi_{a_1,b_1}(g_i)\dots))=a_la_{l-1}\dots a_1g_ib_1\dots b_{l-1}b_l. \end{equation*}
We suppose that Alice chooses parameters $a,b$ in a given finitely generated subgroup $A$ of $G$, and Bob picks up parameters $a,b$ in a finitely generated subgroup $B$ of $G$ to construct their transformations of the form $\varphi_{a,b}$. Under some natural assumptions about $G,A$ and $B,$ we show that an intruder can efficiently calculate the exchanged key $K$ without calculation of the transformations used in the scheme.