文章基本信息

标题：THE MULTIVARIATE QUADRATIC POWER PROBLEM OVER ZN IS NP-COMPLETE
本地全文：下载
作者：Eligijus Sakalauskas
期刊名称：Public Policy And Administration
印刷版ISSN：2029-2872
出版年度：2012
卷号：41
期号：1
页码：33-39
DOI：10.5755/j01.itc.41.1.821
语种：English
出版社：Kaunas University of Technology
摘要：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