MPF problem over modified medial semigroup is NP-complete (Q2333870)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | MPF problem over modified medial semigroup is NP-complete |
scientific article |
Statements
MPF problem over modified medial semigroup is NP-complete (English)
0 references
13 November 2019
0 references
Summary: 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.
0 references
cryptography
0 references
non-commutative cryptography
0 references
one-way functions
0 references
NP-completeness
0 references
key agreement protocol
0 references
0 references
0 references
0 references