# CDH in a group of square matrices

This paper says the CDH problem in a group of square matrices can be solved by a generalized Chinese remainder theorem. I wonder how this problem might be solved?

DH protocol in the cyclic group of matrices $$\langle M \rangle$$, and the matrix $$M$$ is considered as public information. It is assumed that Alice generates a random index $$x$$, calculates the matrix $$M^x$$, and sends it to Bob. In turn, Bob generates a random index $$y$$, calculates the matrix $$M^y$$, and sends it to Alice. Then both subscribers raise the matrices obtained from a partner in their secret powers and calculate the sheared matrix (encryption key) $$K=M^{xy}$$. The matrix $$M$$ must be a high-order matrix (at least 100); ... However, in [3] it has been proved, that Yerosh-Skuratov protocol can easily be cracked based on the generalized Chinese remainder theorem."

• In what set are the elements of the matrix considered? If it's the finite field $\mathbb F_p$, I think this paper applies and shows a reduction of the DLP in $\operatorname{GL}_n(\mathbb F_p)$ to the DLP in $\mathbb F_{p^n}$. But that can't be called "generalized Chinese remainder theorem".
– fgrieu
Sep 15 '21 at 13:58
• My specific problem is the security of Diffi-hellman in the group $\text{GL}(n,2)$! Sep 15 '21 at 16:16
• I think that the Freeman paper could be interpreted as "generalised CRT". The method is to lift into a field $GF(2^m)$ where all of the eigenvalues can be found. In this field, the matrices $M$ and $M^x$ diagonalise to eigenvalues. Then solving $n$ discrete logs with the eigenvalues of $M$ as the generators and the other diagonals as the targets gives $n$ congruences for $x$ modulo the order of the eigenvalue and these can be combined with CRT. Sep 15 '21 at 18:06