Cryptanalysis of novel extended multivariate public key cryptosystem - Xu-yun NIE; Bo LIU; Gang LU; Ting ZHONG (Tongxin xuebao)
The novel extended multivariate public key cryptosystem is a new security enhancement method on multivariate public key cryptosystems,which is proposed by Qiao,et al.A nonlinear invertible transformation was used,named“tame transformation”,on the original multivariate public key cryptosystem to hide its weakness such as linearization equation.However,it is found that if there are many linearization equations satisfied by the original MPKC,there would be many quadratization equations (QE) satisfied by the improved scheme.Given a public key,after finding all QE,a valid cipheretext can be substituted into the QE to derive a set of quadratic equations on the plaintext variable.This exactly reduce the degree of the system wanted to solve.Then the corresponding plaintext can be recovered for a given valid ciphertext combining with Groebner basis method.