Cryptanalysis of Semidirect Product Key Exchange Using Matrices Over Non-Commutative Rings
This work addresses a security problem for cryptographers by revealing incremental vulnerabilities in key exchange protocols.
The paper tackles the vulnerability of the Matrix Action Key Exchange (MAKE) algorithm by showing that protocols using matrices over non-commutative rings, specifically group rings, are also susceptible to a linear algebraic attack under certain conditions.
It was recently demonstrated that the Matrix Action Key Exchange (MAKE) algorithm, a new type of key exchange protocol using the semidirect product of matrix groups, is vulnerable to a linear algebraic attack if the matrices are over a commutative ring. In this note, we establish conditions under which protocols using matrices over a non-commutative ring are also vulnerable to this attack. We then demonstrate that group rings $R[G]$ are examples of non-commutative rings that satisfy these conditions.