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."

  • 1
    $\begingroup$ 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". $\endgroup$
    – fgrieu
    Sep 15, 2021 at 13:58
  • $\begingroup$ My specific problem is the security of Diffi-hellman in the group $\text{GL}(n,2)$! $\endgroup$
    – Amir Amir
    Sep 15, 2021 at 16:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – Daniel S
    Sep 15, 2021 at 18:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.