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

Abstract

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)

CLC Number:

TN918.1

WANG Xin1;SUN Chen2;WANG Xin-mei1. Equivalent keys of multivariate quadratic public key cryptosystem[J].J4, 2009, 36(3): 428-432.

[1]	LUO Fang;ZHOU Xueguang;OU Qingyu. Cryptanalysis of the LBlock using multiple zero-correlation linear approximations [J]. J4, 2014, 41(5): 173-179.
[2]	LIU Jingmei;WANG Yanli;LIANG Bin;ZHAO Senlin. Attack method against the McEliece cryptosystem based on the correlative quasic-cyclic codes set [J]. J4, 2014, 41(2): 15-19+50.
[3]	ZHAO Yongbin;HU Yupu;JIA Yanyan. New design of LFSR based stream ciphers to resist power attack [J]. J4, 2013, 40(3): 172-179+200.
[4]	SUN Jin;HU Yupu. Fully secure attribute-based broadcast encryption [J]. J4, 2012, 39(4): 23-28+154.
[5]	XIAO Heling;CAI Ning;WANG Xiao. Application of quantum LDPC codes to quantum key distribution [J]. J4, 2012, 39(2): 8-11+23.
[6]	LIU Fu-yun;XIAO Hong;XIAO Guo-zhen. Research on finding annihilators of Boolean functions based the algebraic normal form fast transformations [J]. J4, 2009, 36(5): 890-895.
[7]	LI Xue-lian;HU Yu-pu. Algebraic attack on symmetric Boolean functions with a high algebraic immunity [J]. J4, 2009, 36(4): 702-707.
[8]	ZHANG Chuan-rong;ZHANG Yu-qing. Provable security signcryption scheme and its hybrid construction [J]. J4, 2009, 36(4): 756-760.

Equivalent keys of multivariate quadratic public key cryptosystem

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 8

Metrics

Comments

Recommended 8