{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T09:43:58Z","timestamp":1779183838383,"version":"3.51.4"},"reference-count":28,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T00:00:00Z","timestamp":1759449600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["www.mdpi.com"],"crossmark-restriction":true},"short-container-title":["JCP"],"abstract":"<jats:p>Known attacks on the tropical implementation of Stickel protocol involve finding minimal covers for a certain covering problem, and this leads to an exponential growth in the worst case time required to recover the secret key as the used polynomial degree increases. The computational inefficiency of this attack is also observed in practice, unless the number of explored covers is limited, on the expense of the success rate of the attack. Consequently, it can be argued that Alice and Bob can still repel these attacks on tropical Stickel protocol by utilizing very high polynomial degrees, a feasible approach due to the efficiency of tropical operations. The same is true for the implementation of Stickel protocol over some other semirings with idempotent addition (such as the max\u2013min or digital semiring). In this paper, we propose alternative methods to attack the Stickel protocols that avoid solving the covering problem. These methods involve framing the attacks as a mixed integer linear programming (MILP) problem or applying certain heuristic global optimization techniques. We also include a number of numerical experiments to analyze the success rate and the time required to execute the suggested attacks in practice.<\/jats:p>","DOI":"10.3390\/jcp5040082","type":"journal-article","created":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T07:57:27Z","timestamp":1759478247000},"page":"82","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Attacking Tropical Stickel Protocol by MILP and Heuristic Optimization Techniques"],"prefix":"10.3390","volume":"5","author":[{"given":"Sulaiman","family":"Alhussaini","sequence":"first","affiliation":[{"name":"School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4261-7431","authenticated-orcid":false,"given":"Serge\u012d","family":"Sergeev","sequence":"additional","affiliation":[{"name":"School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2624","DOI":"10.1080\/00927872.2013.766827","article-title":"Tropical cryptography","volume":"42","author":"Grigoriev","year":"2013","journal-title":"Commun. Algebra"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/978-3-540-79709-8_29","article-title":"Cryptanalysis of Stickel\u2019s key exchange scheme","volume":"5010","author":"Hirsch","year":"2008","journal-title":"Computer Science\u2014Theory and Applications"},{"key":"ref_3","unstructured":"Stickel, E. (2005, January 4\u20137). A new method for exchanging secret keys. Proceedings of the Third International Conference on Information Technology and Applications (ICITA\u201905), Washington, DC, USA."},{"key":"ref_4","unstructured":"Klir, G.J., and Yuan, B. (1995). Fuzzy Sets and Fuzzy Logic. Theory and Applications, Prentice Hall."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"20240014","DOI":"10.1515\/jmc-2024-0014","article-title":"On implementation of Stickel\u2019s key exchange protocol over max-min and max-T semirings","volume":"18","author":"Alhussaini","year":"2024","journal-title":"J. Math. Cryptol."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Durcheva, M. (2025). Cryptography based on (idempotent) semirings: Abandoning tropicality?. Encyclopedia, 5.","DOI":"10.3390\/encyclopedia5010026"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1515\/jmc-2016-0064","article-title":"Analysis of a key exchange protocol based on tropical matrix algebra","volume":"12","author":"Kotov","year":"2018","journal-title":"J. Math. Cryptol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"20677","DOI":"10.3934\/math.20241005","article-title":"A new semiring and its cryptographic applications","volume":"9","author":"Huang","year":"2024","journal-title":"Aims Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"20240005","DOI":"10.1515\/jmc-2024-0005","article-title":"Tropical cryptography III: Digital signatures","volume":"18","author":"Chen","year":"2024","journal-title":"J. Math. Cryptol."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Golan, J.S. (2000). Semirings and their Applications, Springer.","DOI":"10.1007\/978-94-015-9333-5"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"S\u00e1nchez, \u00c1.O., Portela, D.C., and L\u00f3pez-Ramos, J.A. (2024). On the solutions of linear systems over additively idempotent semirings. Mathematics, 12.","DOI":"10.3390\/math12182904"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Alhussaini, S., and Sergeev, S. (2025). On the security of the initial tropical Stickel protocol and its modification based on Linde-de la Puente matrices. Applicable Algebra in Engineering, Communication and Computing, Springer Nature.","DOI":"10.1007\/s00200-025-00700-x"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1024161","DOI":"10.1155\/2022\/1024161","article-title":"Tropical cryptography based on multiple exponentiation problem of matrices","volume":"2022","author":"Huang","year":"2022","journal-title":"Secur. Commun. Netw."},{"key":"ref_14","first-page":"603","article-title":"Generalized Kotov-Ushakov attack on tropical Stickel protocol based on modified tropical circulant matrices","volume":"60","author":"Alhussaini","year":"2024","journal-title":"Kybernetika"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"727","DOI":"10.21136\/AM.2020.0325-19","article-title":"Modifying the tropical version of Stickel\u2019s key exchange protocol","volume":"65","author":"Muanalifah","year":"2020","journal-title":"Appl. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/S0165-0114(01)00108-7","article-title":"Solvability and unique solvability of max\u2013min fuzzy equations","volume":"124","author":"Gavalec","year":"2001","journal-title":"Fuzzy Sets Syst."},{"key":"ref_17","unstructured":"Zahariev, Z. (2025, September 12). Solving Max-Min Fuzzy Linear Systems of Equations. Algorithm and Software. Annual of \u201cInformatics\u201d section. Union of Scientists in Bulgaria, 6:1\u201316. Available online: http:\/\/e-university.tu-sofia.bg\/e-publ\/files\/12485_SUB-Informatics-2013-6-001-016.pdf."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Peeva, K., and Kyosev, Y. (2004). Fuzzy Relational Calculus\u2014Theory, Applications and Software (with CD-ROM). Advances in Fuzzy Systems\u2014Applications and Theory, World Scientific Publishing Company.","DOI":"10.1142\/5683"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2272","DOI":"10.1016\/j.fss.2008.02.020","article-title":"A note on systems with max\u2013min and max-product constraints","volume":"159","author":"Elbassioni","year":"2008","journal-title":"Fuzzy Sets Syst."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Michalewicz, Z., and Fogel, D. (2000). How to Solve It: Modern Heuristics, Springer.","DOI":"10.1007\/978-3-662-04131-4"},{"key":"ref_21","unstructured":"Tsuzuki, M.d.G., and Martins, T.d.C. (2014). Simulated Annealing: Strategies, Potential Uses and Advantages, Nova Science Publishers, Incorporated."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0167-6377(02)00159-1","article-title":"On the equivalence of linear complementarity problems","volume":"30","author":"Schutter","year":"2002","journal-title":"Oper. Res. Lett."},{"key":"ref_23","unstructured":"Gurobi Optimization, LLC (2023). Gurobi Optimizer Reference Manual, Gurobi Optimization, LLC."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Ponmaheshkumar, A., Kotov, M., and Perumal, R. (2025). Cryptanalysis of a key exchange protocol based on a digital semiring. Communications in Algebra, Taylor and Francis.","DOI":"10.1080\/00927872.2025.2509119"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Andreoni, M. (2024). Forging tropical signatures. Applied Cryptography and Network Security Workshops, Springer Nature.","DOI":"10.1007\/978-3-031-61486-6"},{"key":"ref_26","unstructured":"Brown, D.R.L., and Monico, C. (2025, September 12). More forging (and patching) of tropical signatures. Cryptology ePrint Archive; Paper 2023\/1837. Available online: https:\/\/eprint.iacr.org\/2023\/1837."},{"key":"ref_27","unstructured":"Kim, K.H., and Roush, F.W. (2005). Factorization of polynomials in one variable over the tropical semiring. arXiv."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Butkovi\u010d, P. (2010). Max-Linear Systems: Theory and Algorithms, Springer.","DOI":"10.1007\/978-1-84996-299-5"}],"container-title":["Journal of Cybersecurity and Privacy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2624-800X\/5\/4\/82\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T08:20:01Z","timestamp":1759479601000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2624-800X\/5\/4\/82"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,3]]},"references-count":28,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["jcp5040082"],"URL":"https:\/\/doi.org\/10.3390\/jcp5040082","relation":{},"ISSN":["2624-800X"],"issn-type":[{"value":"2624-800X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,3]]}}}