{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T21:12:15Z","timestamp":1764364335560,"version":"build-2065373602"},"reference-count":38,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2018,2,10]],"date-time":"2018-02-10T00:00:00Z","timestamp":1518220800000},"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>A new enhanced matrix power function (MPF) is presented for the construction of cryptographic primitives. According to the definition in previously published papers, an MPF is an action of two matrices powering some base matrix on the left and right. The MPF inversion equations, corresponding to the MPF problem, are derived and have some structural similarity with classical multivariate quadratic (MQ) problem equations. Unlike the MQ problem, the MPF problem seems to be more complicated, since its equations are not defined over the field, but are represented as left\u2013right action of two matrices defined over the infinite near-semiring on the matrix defined over the certain infinite, additive, noncommuting semigroup. The main results are the following: (1) the proposition of infinite, nonsymmetric, and noncommuting algebraic structures for the construction of the enhanced MPF, satisfying associativity conditions, which are necessary for cryptographic applications; (2) the proof that MPF inversion is polynomially equivalent to the solution of a certain kind of generalized multivariate quadratic (MQ) problem which can be reckoned as hard; (3) the estimation of the effectiveness of direct MPF value computation; and (4) the presentation of preliminary security analysis, the determination of the security parameter, and specification of its secure value. These results allow us to make a conjecture that enhanced MPF can be a candidate one-way function (OWF), since the effective (polynomial-time) inversion algorithm for it is not yet known. An example of the application of the proposed MPF for the Key Agreement Protocol (KAP) is presented. Since the direct MPF value is computed effectively, the proposed MPF is suitable for the realization of cryptographic protocols in devices with restricted computation resources.<\/jats:p>","DOI":"10.3390\/sym10020043","type":"journal-article","created":{"date-parts":[[2018,2,12]],"date-time":"2018-02-12T10:50:38Z","timestamp":1518432638000},"page":"43","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Enhanced Matrix Power Function for Cryptographic Primitive Construction"],"prefix":"10.3390","volume":"10","author":[{"given":"Eligijus","family":"Sakalauskas","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics, Faculty of Mathematics and Natural Sciences, Kaunas University of Technology, Studentu Str. 50-324, LT-51368 Kaunas, Lithuania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,2,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"26","author":"Shor","year":"1997","journal-title":"SIAM J. Comput."},{"key":"ref_2","unstructured":"Garey, M., and Johnson, D. (1979). Computers and Intractability: A Guide to Theory of NP-Completeness, H. Freeman."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Patarin, J., and Goubin, L. (1997, January 11\u201314). Trapdoor One-Way Permutations and Multivariate Polynomials. Proceedings of the First International Conference on Information and Communication Security, LNCS, Beijing, China.","DOI":"10.1007\/BFb0028491"},{"key":"ref_4","unstructured":"Wolf, C. (2002). Hidden Field Equations. (HFE)-Variations and Attacks. [Ph.D. Thesis, Ruhr-University]."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Faugere, J., and Antoine, J. (2003). Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Grobner bases. Advances in Cryptology-CRYPTO, Springer.","DOI":"10.1007\/978-3-540-45146-4_3"},{"key":"ref_6","unstructured":"Yasuda, T., Dahan, X., Huang, Y.-J., Takagi, T., and Sakurai, K. (2018, January 28). MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems. Available online: http:\/\/eprint.iacr.org\/2015\/275.pdf."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Wagner, N.R., and Magyarik, M.R. (1985). A public-key cryptosystem based on the word problem. Advances in Cryptology, Springer.","DOI":"10.1007\/3-540-39568-7_3"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Myasnikov, A.G., Shpilrain, V., and Ushakov, A. (2011). Non-Commutative Cryptography and Complexity of Group-Theoretic Problems, American Mathematical Society.","DOI":"10.1090\/surv\/177"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kumar, G., and Hemraj, S. (2017). Novel Noncommutative Cryptography Scheme Using Extra Special Group. Secur. Commun. Netw., 2017.","DOI":"10.1155\/2017\/9036382"},{"key":"ref_10","unstructured":"Li, J., and Wang, L. (2018, January 28). Noise-Free Symmetric Fully Homomorphic Encryption Based on Noncommutative Rings. Available online: http:\/\/eprint.iacr.org\/2015\/641.pdf."},{"key":"ref_11","unstructured":"Cheng, Q., and Zhuang, L. (arXiv, 2016). LWE from Non-commutative Group Rings, arXiv."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"115","DOI":"10.15388\/Informatica.2007.167","article-title":"Key Agreement Protocol (KAP) Using Conjugacy and Discrete Logarithm Problems in Group Representation Level","volume":"18","author":"Sakalauskas","year":"2007","journal-title":"Informatica"},{"key":"ref_13","unstructured":"Jacobs, K. (2013, March 24). A Survey of Modern Mathematical Cryptology. Available online: http:\/\/trace.tennessee.edu\/utk_chanhonoproj\/1406."},{"key":"ref_14","unstructured":"Sracic, M. (2014, August 04). Quantum Circuits for Matrix Multiplication. Available online: https:\/\/www.math.ksu.edu\/reu\/sumar\/QuantumAlgorithms.pdf."},{"key":"ref_15","unstructured":"Jacobs, K., and Prenner, M. (2011). Cryptanalysis of the Sakalauskas, Tvarijonas, and Raulynaitis Key Agreement Protocol (STR-KAP), Kansas State University. Available online: https:\/\/www.math.ksu.edu\/reu\/sumar\/georgespaper.pdf."},{"key":"ref_16","unstructured":"Ottaviani, V., Zanoni, A., and Regoli, M. (2010, January 26\u201328). Conjugation as public key agreement protocol on mobile cryptography. Proceedings of the 2010 International Conference Security and Cryptography (SECRYPT), Athens, Greece."},{"key":"ref_17","first-page":"31","article-title":"Quantum algorithm for the discrete logarithm problem for matrices over finite group rings","volume":"6","author":"Myasnikov","year":"2012","journal-title":"Groups Complex. Cryptol."},{"key":"ref_18","unstructured":"Sakalauskas, E., and Luk\u0161ys, K. (2007, November 03). Matrix Power S-Box Construction. Available online: http:\/\/eprint.iacr.org\/2007\/214."},{"key":"ref_19","first-page":"2655","article-title":"The Matrix Power Function and its Application to Block Cipher Sbox Construction","volume":"4","author":"Sakalauskas","year":"2007","journal-title":"Int. J. Innov. Comput. Inf. Control"},{"key":"ref_20","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_21","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 Bulgarian Cryptography Days 2012, Sofia, Bulgaria."},{"key":"ref_22","unstructured":"Sakalauskas, E., Listopadskis, N., and Tvarijonas, P. (2008). Key Agreement Protocol (KAP) Based on Matrix Power Function. Information Science and Computing, Book 4 Advanced Studies in Software and Knowledge Engineering, FOI ITHEA."},{"key":"ref_23","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_24","first-page":"119","article-title":"New Asymmetric Cipher Based On Matrix Power Function and Its Implementation in Microprocessors Effciency Investigation","volume":"19","author":"Mihalkovich","year":"2013","journal-title":"Electron. Electr. Eng."},{"key":"ref_25","first-page":"95","article-title":"Implementation analysis of matrix power cipher in embedded systems","volume":"118","author":"Luksys","year":"2012","journal-title":"Electron. Electr. Eng."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Vitkus, P., Sakalauskas, E., Listopadskis, N., and Vitkiene, R. (2012). Microprocessor realization of key agreement protocol (KAP) based on Matrix power function. Electron. Electr. Eng., 117.","DOI":"10.5755\/j01.eee.117.1.1049"},{"key":"ref_27","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_28","unstructured":"Inassaridze, N., Kandelaki, T., and Ladra, M. (arXiv, 2011). Categorical interpretations of some key agreement protocols, arXiv."},{"key":"ref_29","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_30","unstructured":"Krishna, K.V. (2005). Near-Semirings: Theory and Application. [Ph.D. Thesis, IIT Delhi]."},{"key":"ref_31","first-page":"33","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_32","first-page":"1364","article-title":"On the complexity of nonnegative matrix factorization","volume":"3","author":"Vavasis","year":"2009","journal-title":"SIAM J. Optim."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0024-3795(93)90224-C","article-title":"Nonnegative Ranks, Decompositions, and Factorizations of Nonnegative Matrices","volume":"190","author":"Cohen","year":"1993","journal-title":"Linear Algebra Appl."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R., Kannan, R., and Moitra, A. (2012, January 19\u201322). Computing a nonnegative matrix factorization\u2014Provably. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC \u201912, New York, NY, USA.","DOI":"10.1145\/2213977.2213994"},{"key":"ref_35","unstructured":"Patarin, J. (June, January 31). Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Saragossa, Spain."},{"key":"ref_36","unstructured":"Shamir, A., and Kipnis, A. (1999). Cryptanalysis of the HFE Public Key Cryptosystem, Springer."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Courtois, N., Klimov, A., Patarin, J., and Shamir, A. (2000, January 14\u201318). Efficient algorithms for solving overdefined systems of multivariate polynomial equations. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Bruges, Belgium.","DOI":"10.1007\/3-540-45539-6_27"},{"key":"ref_38","unstructured":"Davis, P.J. (1970). Circulant Matrices, Wiley."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/10\/2\/43\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:54:35Z","timestamp":1760194475000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/10\/2\/43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,10]]},"references-count":38,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,2]]}},"alternative-id":["sym10020043"],"URL":"https:\/\/doi.org\/10.3390\/sym10020043","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2018,2,10]]}}}