{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T00:10:36Z","timestamp":1775261436493,"version":"3.50.1"},"reference-count":18,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2018,11,1]],"date-time":"2018-11-01T00:00:00Z","timestamp":1541030400000},"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>This paper is a continuation of our previous publication of enhanced matrix power function (MPF) as a conjectured one-way function. We are considering a problem introduced in our previous paper and prove that tis problem is NP-Complete. The proof is based on the dual interpretation of well known multivariate quadratic (MQ) problem defined over the binary field as a system of MQ equations, and as a general satisfiability (GSAT) problem. Due to this interpretation the necessary constraints to MPF function for cryptographic protocols construction can be added to initial GSAT problem. Then it is proved that obtained GSAT problem is NP-Complete using Schaefer dichotomy theorem. Referencing to this result, GSAT problem by polynomial-time reduction is reduced to the sub-problem of enhanced MPF, hence the latter is NP-Complete as well.<\/jats:p>","DOI":"10.3390\/sym10110571","type":"journal-article","created":{"date-parts":[[2018,11,1]],"date-time":"2018-11-01T11:31:47Z","timestamp":1541071907000},"page":"571","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["MPF Problem over Modified Medial Semigroup Is NP-Complete"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4620-4469","authenticated-orcid":false,"given":"Eligijus","family":"Sakalauskas","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics, Kaunas University of Technology, LT-44249 Kaunas, Lithuania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8661-3021","authenticated-orcid":false,"given":"Aleksejus","family":"Mihalkovich","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Kaunas University of Technology, LT-44249 Kaunas, Lithuania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,11,1]]},"reference":[{"key":"ref_1","first-page":"72","article-title":"Asymmetric cipher based on MPF and its security parameters evaluation","volume":"Volume 53","author":"Mihalkovich","year":"2012","journal-title":"Proceedings of the Lithuanian Mathematical Society"},{"key":"ref_2","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":"Elektron. Elektrotech."},{"key":"ref_3","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, World Scientific."},{"key":"ref_4","unstructured":"Sakalauskas, E., and Luksys, K. (2018, October 26). Matrix Power S-Box Construction. IACR Cryptology ePrint Archive 2007. Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.78.2327&rep=rep1&type=pdf."},{"key":"ref_5","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_6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.5755\/j01.itc.41.1.821","article-title":"The multivariate quadratic power problem over Zn is NP-Complete","volume":"41","author":"Sakalauskas","year":"2012","journal-title":"Inf. Technol. Control"},{"key":"ref_7","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_8","doi-asserted-by":"crossref","unstructured":"Sakalauskas, E., Mihalkovich, A., and Ven\u010dkauskas, A. (2017). Improved asymmetric cipher based on matrix power function with provable security. Symmetry, 9.","DOI":"10.3390\/sym9010009"},{"key":"ref_9","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_10","doi-asserted-by":"crossref","unstructured":"Sakalauskas, E. (2018). Enhanced Matrix Power Function for Cryptographic Primitive Construction. Symmetry, 10.","DOI":"10.3390\/sym10020043"},{"key":"ref_11","unstructured":"Garey, M.R., and Johnson, D.S. (2002). Computers and Intractability, WH Freeman."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Patarin, J., and Goubin, L. (1997, January 11\u201314). Trapdoor one-way permutations and multivariate polynomials. Proceedings of the International Conference on Information and Communications Security, Beijing, China.","DOI":"10.1007\/BFb0028491"},{"key":"ref_13","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"},{"key":"ref_14","unstructured":"Davis, P.J. (1970). Circulant Matrices, Wiley."},{"key":"ref_15","unstructured":"Sakalauskas, E., and Mihalkovich, A. (2012, January 20\u201321). Candidate One-Way Function Based on Matrix Power Function with Conjugation Constraints. Proceedings of the Conference proceedings Bulgarian Cryptography Days 2012, Sofia, Bulgaria."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Liu, J., Zhang, H., and Jia, J. (2016, January 4\u20136). A linear algebra attack on the non-commuting cryptography class based on matrix power function. Proceedings of the International Conference on Information Security and Cryptology, Beijing, China.","DOI":"10.1007\/978-3-319-54705-3_21"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0021-8693(69)90013-1","article-title":"On medial semigroups","volume":"12","author":"Chrislock","year":"1969","journal-title":"J. Algebra"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0004-3702(92)90009-M","article-title":"Structure identification in relational data","volume":"58","author":"Dechter","year":"1992","journal-title":"Artif. Intell."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/10\/11\/571\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T22:55:48Z","timestamp":1775256948000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/10\/11\/571"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,1]]},"references-count":18,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2018,11]]}},"alternative-id":["sym10110571"],"URL":"https:\/\/doi.org\/10.3390\/sym10110571","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,1]]}}}