摘要：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 Z n , denoted by MQP( Z n ), where n is positive integer. Two sequential polynomial-time reductions from known NP-complete multivariate quadratic (MQ) problem over the field Z 2 , i.e. MQ( Z 2 ) to MQP( Z n ) are constructed. It is proved that certain restricted MQP( Z n ) problem over some subgroup of Z n is equivalent to MQ( Z 2 ) problem. This allow us to prove that MQP( Z n ) 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.
关键词：NP-complete problems; multivariate quadratic power (MQP) problem; one-way function (OWF); cryptography
