MPF problem over modified medial semigroup is NP-complete

DOI10.3390/SYM10110571MaRDI QIDQ2333870zbMATH OpenOpenAlexFDO

Authors Eligijus Sakalauskas, Aleksejus Mihalkovich

Publication date 13 November 2019

Published in Symmetry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/sym10110571

zbMATH Keywords

cryptographykey agreement protocolnon-commutative cryptographyNP-completenessone-way functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Cryptography (94A60)

Review text

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.

Recommendations

• On Some $\mathcal{NP}$ -complete SEFE Problems
• MNP: A class of NP optimization problems
• The minimal realization problem in the max-plus semiring and Pisot's problem are NP-hard
• MNP: A class of NP optimization problems
• The complexity of the equation solvability problem over semipattern groups
• NP-completeness results for edge modification problems
• The transposition median problem is NP-complete
• Complete problems for monotone NP
• DP-Complete Problems Derived from Extremal NP-Complete Properties
• Semidefinite programming and its applications to NP problems

Cites work

• A linear algebra attack on the non-commuting cryptography class based on matrix power function
• Asymmetric cipher based on MPF and its security parameters evaluation
• Enhanced matrix power function for cryptographic primitive construction
• scientific article; zbMATH DE number 1185220 (Why is no real title available?)
• scientific article; zbMATH DE number 1107703 (Why is no real title available?)
• Improved asymmetric cipher based on matrix power function resistant to linear algebra attack
• Improved asymmetric cipher based on matrix power function with provable security
• New asymmetric cipher of non-commuting cryptography class based on matrix power function
• On medial semigroups
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Structure identification in relational data
• The complexity of satisfiability problems

Cited in

(1)

• Enhanced matrix power function for cryptographic primitive construction

This page was built for publication: MPF problem over modified medial semigroup is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333870)