Matrix Polynomial Attack on the Megrelishvili Key Exchange Protocol

In this article we explain what the Megrelishvili Key Exchange Protocol (MKE) is and compare it briefly to the older Diffie-Hellman Key Exchange Protocol. We clarify how the security of the MKE relates to the hardness of the Megrelishvili Vector-Matrix Problem (MVMP) and also to a generalization of this problem, introduced by us, which we call the Matrix Polynomial Problem (MPP). There were previous sub-exponential time attacks on the MKE [AW16, AMP18], the first applying to arbitrary instances and the latter requiring the public matrix M to be diagonalizable — as well as an attack on the one-way function used in the MKE [Meg14] that required special conditions, but when applicable would allow to break the protocol in polynomial time according to our running-time analysis. Here we adopt a bottom-up approach to construct for the first time, as far as our review of the relevant literature reveals, a polynomial time algorithm that solves any instance of the MKE through its reduction to a MPP. We also introduce some key concepts from linear algebra and Krylov subspace theory into the context of the MKE, allowing for a clearer understanding of our attack.