{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:56:31Z","timestamp":1767930991645,"version":"3.49.0"},"reference-count":18,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T00:00:00Z","timestamp":1759795200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,12,2]]},"abstract":"<jats:p>\n                    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\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>M<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    to be diagonalizable \u2014 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.\n                  <\/jats:p>","DOI":"10.62056\/akmpdk5vt","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:39:47Z","timestamp":1767915587000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Matrix Polynomial Attack on the Megrelishvili Key Exchange Protocol"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-8572-7072","authenticated-orcid":false,"given":"Raul","family":"de Assis","sequence":"first","affiliation":[{"name":"CEPESC","place":["Bras\u00edlia, 70.610-905, Brazil"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0776-034X","authenticated-orcid":false,"given":"Thiago","family":"do R\u00eago Sousa","sequence":"additional","affiliation":[{"name":"CEPESC","place":["Bras\u00edlia, 70.610-905, Brazil"]}]}],"member":"48349","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"ref1:arzaki2016collision","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/ICACSIS.2016.7872728","article-title":"Collision algorithms for breaking Megrelishvili protocol:\n  Theory and numerical experiments","author":"Muhammad Arzaki","year":"2016"},{"key":"ref2:arzaki2018breaking","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/971\/1\/012025","article-title":"Breaking Megrelishvili protocol using matrix\n  diagonalization","volume":"971","author":"Muhammad Arzaki","year":"2018"},{"key":"ref3:megrelishvili2014analysis","article-title":"Analysis of the Matrix One-Way Function and Two Variants of\n  Its Implementation.","volume":"43","author":"Richard P Megrelishvili","year":"2014","journal-title":"Computer Science & Telecommunications"},{"key":"ref4:Diffie1976a","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New Directions in Cryptography","volume":"22","author":"Whitfield Diffie","year":"1976","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref5:megrelishvili2006construction","first-page":"29","article-title":"On the construction of secret and public-key cryptosystems","volume":"11","author":"R Megrelishvili","year":"2006","journal-title":"Appl. Math., Inform. Mech"},{"key":"ref6:arzaki2016elementary","doi-asserted-by":"publisher","first-page":"11","DOI":"10.21108\/INDOJC.2016.1.1.52","article-title":"Elementary algorithms analysis of Megrelishvili protocol","volume":"1","author":"Muhammad Arzaki","year":"2016","journal-title":"Indonesia Journal on Computing (Indo-JC)"},{"key":"ref7:arzaki2018strengthening","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1109\/ICoICT.2018.8528731","article-title":"Strengthening Megrelishvili Protocol Against\n  Man-in-the-Middle Attack","author":"Muhammad Arzaki","year":"2018"},{"key":"ref8:arzaki2017extending","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/ICoICT.2017.8074690","article-title":"Extending Megrelishvili protocol for multi-party key\n  agreement","author":"Muhammad Arzaki","year":"2017"},{"key":"ref9:Arzaki2017Generalizations","doi-asserted-by":"publisher","first-page":"55","DOI":"10.21108\/INDOJC.2017.2.2.179","article-title":"On the Generalizations of Megrelishvili Protocol for Group\n  Key Distribution","volume":"2","author":"Muhammad Arzaki","year":"2017","journal-title":"Indonesian Journal on Computing (Indo-JC)"},{"key":"ref10:arzaki2019constructing","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/ICoICT.2019.8835378","article-title":"Constructing a One-time and a Few-time Digital Signature\n  Schemes from the Hardness of Megrelishvili Vector-Matrix Problem","author":"Muhammad Arzaki","year":"2019"},{"key":"ref11:ismail2021quantum","doi-asserted-by":"publisher","first-page":"1720","DOI":"10.1007\/s10773-021-04794-0","article-title":"Quantum spin half algebra and generalized megrelishvili\n  protocol for confidentiality of digital images","volume":"60","author":"A Haj Ismail","year":"2021","journal-title":"International Journal of Theoretical Physics"},{"key":"ref12:waseem2021novel","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/s10773-020-04694-9","article-title":"A novel hybrid secure confidentiality mechanism for medical\n  environment based on Kramer\u2019s spin principle","volume":"60","author":"Hafiz Muhammad Waseem","year":"2021","journal-title":"International Journal of Theoretical Physics"},{"key":"ref13:menezeswu1997","first-page":"23","article-title":"The discrete logarithm problem in GL(n, q)","volume":"47","author":"A. J. Menezes","year":"1997","journal-title":"Ars Combinatoria"},{"key":"ref14:shor1994algorithms","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/SFCS.1994.365700","article-title":"Algorithms for quantum computation: discrete logarithms and\n  factoring","author":"Peter W Shor","year":"1994"},{"key":"ref15:childs2017lecture","article-title":"Lecture notes on quantum algorithms","volume":"5","author":"Andrew M Childs","year":"2017","journal-title":"Lecture notes at University of Maryland"},{"key":"ref16:dumas2005efficient","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1145\/1073884.1073905","article-title":"Efficient computation of the characteristic polynomial","author":"Jean-Guillaume Dumas","year":"2005"},{"key":"ref17:neiger2024computing","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/3666000.3669715","article-title":"Computing Krylov iterates in the time of matrix\n  multiplication","author":"Vincent Neiger","year":"2024"},{"key":"ref18:aho1974design","volume-title":"The design and analysis of computer algorithms","author":"Alfred V Aho","year":"1974"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:40:31Z","timestamp":1767915631000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/4\/16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":18,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,1,8]]}},"URL":"https:\/\/doi.org\/10.62056\/akmpdk5vt","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-10-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-4-33"}}