Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Assis et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: