THE MULTIVARIATE QUADRATIC POWER PROBLEM OVER ZN IS NP-COMPLETE
|
| Title | THE MULTIVARIATE QUADRATIC POWER PROBLEM OVER ZN IS NP-COMPLETE |
| Authors | |
| 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 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 |
| Publisher | Kaunas University of Technology |
| Date | 2012-04-24 |
| Source | Informacinės technologijos ir valdymas Vol 41, No 1 (2012) |
| Rights | Copyright terms are indicated in the Republic of Lithuania Law on Copyright and Related Rights, Articles 4-37. |