| Title |
The multivariate quadratic power problem over Zn is NP-complete |
| Another Title |
NP pilnoji daugelio kintamųjų laipsnių kvadratų problema virš Zn. |
| Authors |
Sakalauskas, Eligijus |
| DOI |
10.5755/j01.itc.41.1.821 |
| Full Text |
|
| Is Part of |
Informacinės technologijos ir valdymas = Information technology and control.. Kaunas : Technologija. 2012, t. 41, Nr. 1, p. 33-39.. ISSN 1392-124X. eISSN 2335-884X |
| Keywords [eng] |
NP-complete problem ; Multivariate quadratic power problem ; One-way function ; Cryptography |
| Abstract [eng] |
In this paper a new NP-complete problem, named as multivariate quadratic power (MQP) problem, is presented. This problem is formulated as a solution of multivariate quadratic power system of equations over the semigroup (monoid) Zn and is denoted by MQP(Zn), where n is a positive integer. Two sequential polynomial-time reductions from the 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 allows us to prove that MQP(Zn) is NP-complete also. The MQP problem is related to matrix power function (MPF) which was used for construction of several cryptographic protocols. We expect that the NP-complete problem announced here could be used to create new candidate one-way functions (OWF) and to construct new cryptographic primitives. |
| Published |
Kaunas : Technologija |
| Type |
Journal article |
| Language |
English |
| Publication date |
2012 |
| CC license |
|
