新扩展多变量公钥密码方案的安全性分析

新扩展多变量公钥密码方案是乔等提出的一种多变量公钥密码体制的安全性增强方案。该方案引入了一个非线性“温顺变换”，试图隐藏原始方案的弱点，如线性化方程。然而，分析表明，若原始方案满足线性化方程，则改进方案必然满足二次化方程。给定公钥，在找到所有的二次化方程之后，将要破解的合法密文代入到二次化方程中，可以得到关于明文变量的二次方程。这降低了要求解的方程组的次数。结合Groebner基方法，可以快速地恢复合法密文相应的明文。

Cryptanalysis of novel extended multivariate public key cryptosystem

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.