MPF Problem over Modified Medial Semigroup Is NP-Complete
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 mul...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-11-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/10/11/571 |
| _version_ | 1817992500339539968 |
|---|---|
| author | Eligijus Sakalauskas Aleksejus Mihalkovich |
| author_facet | Eligijus Sakalauskas Aleksejus Mihalkovich |
| author_sort | Eligijus Sakalauskas |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-14T01:27:25Z |
| format | Article |
| id | doaj.art-9277eaa97ed34f75ac0efb76e67066e0 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-04-14T01:27:25Z |
| publishDate | 2018-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-9277eaa97ed34f75ac0efb76e67066e02022-12-22T02:20:22ZengMDPI AGSymmetry2073-89942018-11-01101157110.3390/sym10110571sym10110571MPF Problem over Modified Medial Semigroup Is NP-CompleteEligijus Sakalauskas0Aleksejus Mihalkovich1Department of Applied Mathematics, Kaunas University of Technology, LT-44249 Kaunas, LithuaniaDepartment of Applied Mathematics, Kaunas University of Technology, LT-44249 Kaunas, LithuaniaThis 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.https://www.mdpi.com/2073-8994/10/11/571cryptographynon-commutative cryptographyone-way functionsNP-Completenesskey agreement protocol |
| spellingShingle | Eligijus Sakalauskas Aleksejus Mihalkovich MPF Problem over Modified Medial Semigroup Is NP-Complete Symmetry cryptography non-commutative cryptography one-way functions NP-Completeness key agreement protocol |
| title | MPF Problem over Modified Medial Semigroup Is NP-Complete |
| title_full | MPF Problem over Modified Medial Semigroup Is NP-Complete |
| title_fullStr | MPF Problem over Modified Medial Semigroup Is NP-Complete |
| title_full_unstemmed | MPF Problem over Modified Medial Semigroup Is NP-Complete |
| title_short | MPF Problem over Modified Medial Semigroup Is NP-Complete |
| title_sort | mpf problem over modified medial semigroup is np complete |
| topic | cryptography non-commutative cryptography one-way functions NP-Completeness key agreement protocol |
| url | https://www.mdpi.com/2073-8994/10/11/571 |
| work_keys_str_mv | AT eligijussakalauskas mpfproblemovermodifiedmedialsemigroupisnpcomplete AT aleksejusmihalkovich mpfproblemovermodifiedmedialsemigroupisnpcomplete |