MQ公钥密码体制等价密钥分析  

Equivalent keys of multivariate quadratic public key cryptosystem

作　　者：王鑫[1] 孙晨[2] 王新梅[1] 

机构地区：[1]西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安710071 [2]空军工程大学导弹学院,陕西三原713800

出　　处：《西安电子科技大学学报》2009年第3期428-432,共5页Journal of Xidian University

基　　金：国家自然科学基金资助(90604009,60503010)

摘　　要：MQ公钥密码体制存在多个私钥对应同一个公钥的问题.应用高斯不变算子对私钥空间进行等价分类,给出了任一私钥的等价类中所含元素的个数与明密文分量之间的关系式.该式表明,对任一公钥有指数级个私钥与之对应,从而使私钥(进而公钥)空间大量减少.同时,还给出了私钥的仿射结构的标准形,该形式具有稀疏性,从而能够有效地减少计算量,提高存储效率.最后,以R-SE(2)签名体制为例,分析了分层结构对体制安全性的影响.The multivariate quandratic cryptosystem has the problem that many superflous private keys correspond to the same public key. By applying the Gauss Sustainer, the private key space is partitioned into equivalence classes. And then, a relationship between the number of elements in any equivalence private key class and plaintext （ciphertext） is established. This formula shows the number of private keys corresponding to any given public key is exponential. Hence, the private （further the public） key space is reduced greatly. Moreover, the normal form of affine transformations of the private key is derived. It has the sparse characteristic, which will reduce computing complexity and improve the storage efficiency. Finally, the R-SE（2） public key signature scheme is taken for an example, and the security performance of this scheme affected by the step-structure is analyzed.

关 键 词：多变量公钥密码 代数分析 等价密钥 高斯不变算子 R-SE(2) 

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