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)

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)