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

Cryptanalysis of novel extended multivariate public key cryptosystem

作　　者：聂旭云[1,2] 刘波[1] 鲁刚[3] 钟婷[1] 

机构地区：[1]电子科技大学信息与软件工程学院,四川成都611731 [2]中国科学院信息工程研究所信息安全国家重点实验室,北京100093 [3]电子科技大学计算机科学与工程学院,四川成都611731

出　　处：《通信学报》2015年第6期60-65,共6页Journal on Communications

基　　金：国家重点基础研究发展计划("973"计划)基金资助项目(2013CB834203);国家自然科学基金资助项目(61370026;61472064)~~

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

关 键 词：多变量公钥密码系统 二次化方程 线性化方程 温顺变换 代数攻击 

分 类 号：TN918.1[电子电信—通信与信息系统]