CDH in a group of square matrices

Amir Amir

1/15/23, 1:12 PM

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

0 + 0

discrete-logarithm

diffie-hellman

fgrieu

1/15/23, 1:58 PM

In what set are the elements of the matrix considered? If it's the finite field $\mathbb F_p$, I think this [paper](http://theory.stanford.edu/~dfreeman/papers/discretelogs.pdf) 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".

Amir Amir

1/15/23, 4:16 PM

My specific problem is the security of Diffi-hellman in the group $\text{GL}(n,2)$!

Daniel S

1/15/23, 6:06 PM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: CDH in a group of square matrices

TH: CDH ในกลุ่มของเมทริกซ์สี่เหลี่ยม

RO: CDH într-un grup de matrici pătrate

RU: CDH в группе квадратных матриц

VI: CDH trong nhóm ma trận vuông

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.