THE MULTIVARIATE QUADRATIC POWER PROBLEM OVER ZN IS NP-COMPLETE

Authors

  • Eligijus Sakalauskas Department of Applied Mathematics, Kaunas University of Technology

DOI:

https://doi.org/10.5755/j01.itc.41.1.821

Keywords:

NP-complete problems, multivariate quadratic power (MQP) problem, one-way function (OWF), cryptography

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

Downloads

Published

2012-04-09

Issue

Section

Articles