Cryptanalysis of a Key Exchange Protocol Based on Commuting Matrices

A key exchange protocol is considered unsafe. The scheme is based on a set of m commuting square singular matrices of dimension n×n over a finite field, and its security is claimed to rely on the hardness of the matrix version discrete logarithm problem. However, the proposal's design allows for a clean attack strategy. We show that the key exchange protocol is vulnerable to a linear algebra attack which only requires polynomial time to obtain the equivalent keys for all given public keys. We conduct a detailed analysis on the attack method and provide some improved suggestions on the key exchange protocol based on commuting matrices.