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

Abstract:

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.

Key words: multivariate public key cryptosystem, algebraic cryptanalysis, equivalent keys, Gauss sustainer, R-SE(2)