{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:41:45Z","timestamp":1760179305909,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T00:00:00Z","timestamp":1597881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>In this paper we present a cryptographic primitive based on non-commutative cryptography. This primitive is used for key exchange protocol (KEP) construction. We prove that the security of this primitive relies on a nondeterministic polynomial complete (NP-Complete) decisional problem. Recently there are no known quantum cryptanalysis algorithms effectively solving NP-Complete problems. So far, KEPs are widely used in secure communication channel creation, e.g., in hypertext transfer protocol secure (https:\/\/) and are based on traditional cryptographic primitives representing commutative cryptography. However, the security of these protocols does not rely on NP-Complete problems and hence, according to P. W. Shorr, they are vulnerable to quantum cryptanalysis. We use one of seven non-commuting groups of order 16 which is not isomorphic to any other group to define a platform group for a key exchange protocol based on previously considered matrix power function (MPF). By investigating basic properties on the group M16 and their implementation for our goals we fix the order of actions in MPF from left to right. Furthermore, we define a special form of the base matrix and separate templates for left and right power matrices. Using properties of the specified templates and Schaeffer criteria we prove that the security of the proposed key exchange relies on an NP-Complete decisional problem.<\/jats:p>","DOI":"10.3390\/sym12091389","type":"journal-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T21:13:42Z","timestamp":1597958022000},"page":"1389","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Key Exchange Protocol Defined over a Non-Commuting Group Based on an NP-Complete Decisional Problem"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8661-3021","authenticated-orcid":false,"given":"Aleksejus","family":"Mihalkovich","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics, Kaunas University of Technology, Studentu str. 50-324, 44249 Kaunas, Lithuania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4620-4469","authenticated-orcid":false,"given":"Eligijus","family":"Sakalauskas","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Kaunas University of Technology, Studentu str. 50-324, 44249 Kaunas, Lithuania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1619-8720","authenticated-orcid":false,"given":"Kestutis","family":"Luksys","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Kaunas University of Technology, Studentu str. 50-324, 44249 Kaunas, Lithuania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New directions in cryptography","volume":"22","author":"Diffie","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1090\/S0025-5718-1987-0866109-5","article-title":"Elliptic curve cryptosystems","volume":"48","author":"Koblitz","year":"1987","journal-title":"Math. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1137\/S0036144598347011","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"41","author":"Shor","year":"1999","journal-title":"SIAM Rev."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Gawiejnowicz, S. (2020). NP-complete problems. Models and Algorithms of Time-Dependent Scheduling, Springer.","DOI":"10.1007\/978-3-662-59362-2"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Patarin, J. (1996). Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms. International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/3-540-68339-9_4"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Kipnis, A., and Shamir, A. (1999). Cryptanalysis of the HFE public key cryptosystem by relinearization. Annual International Cryptology Conference, Springer.","DOI":"10.1007\/3-540-48405-1_2"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Courtois, N.T. (2001). The security of hidden field equations (HFE). Cryptographers\u2019 Track at the RSA Conference, Springer.","DOI":"10.1007\/3-540-45353-9_20"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Faugere, J.C., and Joux, A. (2003). Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gr\u00f6bner bases. Annual International Cryptology Conference, Springer.","DOI":"10.1007\/978-3-540-45146-4_3"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Regev, O. (2009). Lattice-based cryptography. Post-Quantum Cryptography, Springer.","DOI":"10.1007\/978-3-540-88702-7_5"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Bindel, N., Buchmann, J., and Kr\u00e4mer, J. (2016, January 16). Lattice-based signature schemes and their sensitivity to fault attacks. Proceedings of the 2016 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), Santa Barbara, CA, USA.","DOI":"10.1109\/FDTC.2016.11"},{"key":"ref_12","unstructured":"Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J.S., and Park, C. (2010). New public-key cryptosystem using braid groups. Annual International Cryptology Conference, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"287","DOI":"10.4310\/MRL.1999.v6.n3.a3","article-title":"An algebraic method for public-key cryptography","volume":"6","author":"Anshel","year":"1999","journal-title":"Math. Res. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/s00200-006-0009-6","article-title":"The conjugacy search problem in public key cryptography: Unnecessary and insufficient","volume":"17","author":"Shpilrain","year":"2006","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"ref_15","unstructured":"Sakalauskas, E., Listopadskis, N., and Tvarijonas, P. (2008). Key agreement protocol (KAP) based on matrix power function. Advanced Studies in Software and Knowledge Engineering, Institute of Information Theories and Applications FOI ITHEA. Information Science and Computing."},{"key":"ref_16","first-page":"2655","article-title":"Matrix power function and its application to block cipher s-box construction","volume":"8","author":"Sakalauskas","year":"2012","journal-title":"Int. J. Inn. Comp. Inf. Contr."},{"key":"ref_17","first-page":"72","article-title":"Asymmetric cipher based on MPF and its security parameters evaluation","volume":"53","author":"Mihalkovich","year":"2012","journal-title":"Proc. Lith. Math. Soc. Ser. A"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"119","DOI":"10.5755\/j01.eee.19.10.5906","article-title":"New asymmetric cipher based on matrix power function and its implementation in microprocessors efficiency investigation","volume":"19","author":"Mihalkovich","year":"2013","journal-title":"Elektronika ir Elektrotechnika"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"283","DOI":"10.15388\/Informatica.2014.15","article-title":"New asymmetric cipher of non-commuting cryptography class based on matrix power function","volume":"25","author":"Sakalauskas","year":"2014","journal-title":"Informatica"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Liu, J., Zhang, H., and Jia, J. (2016). A linear algebra attack on the non-commuting cryptography class based on matrix power function. International Conference on Information Security and Cryptology, Springer.","DOI":"10.1007\/978-3-319-54705-3_21"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"517","DOI":"10.15388\/Informatica.2017.142","article-title":"Improved Asymmetric Cipher Based on Matrix Power Function Resistant to Linear Algebra Attack","volume":"28","author":"Sakalauskas","year":"2017","journal-title":"Informatica"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Mihalkovich, A., and Levinskas, M. (2019). Investigation of Matrix Power Asymmetric Cipher Resistant to Linear Algebra Attack. International Conference on Information and Software Technologies 2019, Springer.","DOI":"10.1007\/978-3-030-30275-7_16"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Sakalauskas, E. (2018). Enhanced matrix power function for cryptographic primitive construction. Symmetry, 10.","DOI":"10.3390\/sym10020043"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Sakalauskas, E., and Mihalkovich, A. (2018). MPF Problem over Modified Medial Semigroup Is NP-Complete. Symmetry, 10.","DOI":"10.3390\/sym10110571"},{"key":"ref_25","first-page":"7","article-title":"On the associativity property of MPF over M16","volume":"59","author":"Mihalkovich","year":"2018","journal-title":"Proc. Lith. Math. Soc. Ser. A"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"2631","DOI":"10.1090\/S0002-9939-96-03345-X","article-title":"Automatic realizability of Galois groups of order 16","volume":"124","author":"Grundman","year":"1996","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_27","first-page":"289","article-title":"Groups of order 16 as Galois groups","volume":"13","author":"Grundman","year":"1995","journal-title":"Expo. Math"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s10958-013-1588-y","article-title":"Categorical interpretations of some key agreement protocols","volume":"195","author":"Inassaridze","year":"2013","journal-title":"J. Math. Sci."},{"key":"ref_29","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability, Freeman."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J. (1978, January 1\u20133). The complexity of satisfiability problems. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA.","DOI":"10.1145\/800133.804350"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/9\/1389\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:03:57Z","timestamp":1760177037000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/9\/1389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,20]]},"references-count":30,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["sym12091389"],"URL":"https:\/\/doi.org\/10.3390\/sym12091389","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2020,8,20]]}}}