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

Equivalent keys of multivariate quadratic public key cryptosystem

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.