THE MULTIVARIATE QUADRATIC POWER PROBLEM OVER ZN IS NP-COMPLETE

Abstract

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₂, i.e. MQ(Z₂) 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₂) 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.

DOI: http://dx.doi.org/10.5755/j01.itc.41.1.821