摘要：New NP-complete problem, named as multivariate quadratic power (MQP) problem, is presented. It is based on solution of multivariate quadratic power system of equations over the semigroup Zn, denoted by MQP(Zn), where n is positive integer. Two sequential polynomial-time reductions from known NP-complete multivariate quadratic (MQ) problem over the field Z2, i.e. MQ(Z2) to MQP(Zn) are constructed. It is proved that certain restricted MQP(Zn) problem over some subgroup of Zn is equivalent to MQ(Z2) problem. This allow us to prove that MQP(Zn) is NP-complete also.MQP problem is linked to some author’s previously declared matrix power function (MPF) used for several cryptographic protocols construction. Obtained NP-complete problem will be used to create new candidate one-way function (OWF) based on MPF for new cryptographic primitives’ construction.DOI: http://dx.doi.org/10.5755/j01.itc.41.1.821
关键词：NP-complete problems; multivariate quadratic power (MQP) problem; one-way function (OWF); cryptography
Loading...
