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

doi:10.11959/j.issn.1000-436x.2015182

Journal on Communications ›› 2015, Vol. 36 ›› Issue (6): 60-65.doi: 10.11959/j.issn.1000-436x.2015182

• Academic paper • Previous Articles Next Articles

Cryptanalysis of novel extended multivariate public key cryptosystem

Xu-yun NIE^1,²,Bo LIU¹,Gang LU³,Ting ZHONG¹

¹ School of Information and Software Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China
² State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China
³ School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China

Online:2015-06-25 Published:2017-05-11
Supported by:
The National Natural Basic Research Program of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China

Abstract

Abstract:

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.

Key words: multivariate public key cryptosystems, quadratic equations, linear equations, tame transformation, algebraic attack

Xu-yun NIE,Bo LIU,Gang LU,Ting ZHONG. Cryptanalysis of novel extended multivariate public key cryptosystem[J]. Journal on Communications, 2015, 36(6): 60-65.

Figures/Tables 2

References 10

[1]	DING J T , GOWER J , SCHMIDT D . Multivariate Public Key Cryptosystems[M]. Berlin: Springer-VerlagPress, 2006.
[2]	PATARIN J . Cryptanalysis of the Matsumoto and Imai public key scheme of eurocrypt 1988[A]. Proceedings of Advances in Cryptology,Crypto 1995[C]. Santa Barbara,California,USA, 1995. 248-261.
[3]	MATSUMOTO T , IMAI H . Public quadratic polynomial-tuples for efficient signature verification and message encryption[A]. Proceedings of Advances in Cryptology- Eurocrypt’88[C]. Davos,Switzerland, 1988. 419-453.
[4]	DING J T,HU L , NIE X Y , LI J Y,WAGNERJ . High order linearization equation (HOLE) attack on multivariate public key cryptosystems[A]. Proceedings of Public key Cryptography-PKC 2007[C]. Beijing,China, 2007. 233-248.
[5]	WANG L C,YANG B Y , HU Y H , LAI F . A medium-field multivariate public-key encryption scheme[A]. Proceedings of Topics in Cryptology,CT-RSA 2006[C]. San Jose,CA,USA, 2006. 132-149.
[6]	WANG X,FENG F , WANG X , WANG Q . A more secure MFE multivariate public key encryption scheme[J]. International Journal of Computer Science and Applications, 2009,6(3): 1-9.
[7]	CAO W W,NIE X Y,HU L , TANG X L , DING J T . Cryptanalysis of two quartic encryption schemes and one improved MFE scheme[A]. Proceedings of Cryptology,PQCrypto 2010[C]. Darmstadt,Germany, 2010. 41-60.
[8]	乔帅庭, 李益发, 韩文报 . 新扩展多变量公钥密码方案[J]. 通信学报, 2014,35(4): 148-154. QIAO S T , LI Y F , HAN W B . Novel extended multivariate public key cryptosystem[J]. Journal on Communications, 2014,35(4): 148-154.
[9]	NIE X Y,PETZOLDT A , BUCHMANN J , LI F G . Linearization equation attack on 2-layer nonlinear piece in hand method[J]. IEICE Transactions , 2014,97(9): 1952-1961 .
[10]	DIENE A,DING J T,GOWER J E , HODGES T J , YIN Z J . Dimension of the linearization equations of the Matsumoto-Imai cryptosystems[A]. Proceedings of Code and Cryptography—WCC 2005[C]. Bergen,Norway, 2005. 242-251.

Metrics

Recommended 0

No Suggested Reading articles found!

n	d	θ	D	D'	T1/s	T2/s	T3/s	合计/s
17	5	4	16	16	6.6	18.8	0.015	38.4
17	8	4	16	16	6.5	19.2	0	39.0
17	8	16	16	16	6.4	19.1	0	38.5
20	5	4	15	15	16.7	73.6	0.016	120.6
20	10	4	16	16	15.9	73.8	0.015	122.8
20	10	16	16	16	16.6	73.7	0.016	122.9
23	5	4	22	22	37.1	240.4	0.015	375.3
23	11	4	22	22	37.6	240.3	0.016	375.5
23	11	22	22	22	37.5	240.5	0.031	375.6
26	5	4	24	24	73.5	700.0	0.015	993.5
26	12	4	24	24	77.5	702.2	0.047	1 001.6
26	12	24	24	24	78.3	699.9	0.016	999.4
33	7	4	32	32	313.3	5 232.1	0.016	6 655.3
33	16	4	32	32	318.2	5 391.5	0.047	6 855.3
33	16	32	32	32	320.0	5 332.0	0.016	6 802.4	6 802.4
注：T1：生成明密对时间；T2：得到二次化方程的时间；T3：Groebner基求解时间

n	d	θ	T1/s	T2/s
14	5	4	0.015	0.234
15	5	5	0.078	0.266
17	5	4	0.015	103.015
18	5	4	0.016	442.391

Cryptanalysis of novel extended multivariate public key cryptosystem

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 10

Related Articles 6

Metrics

Recommended 0

[1]	Xiangmin JI,Bo ZHAO,Jinhui LIU,Jianwei JIA,Huanguo ZHANG,Shuang XIANG. WSN key recovery attack based on symmetric matrix decomposition [J]. Journal on Communications, 2018, 39(10): 87-96.
[2]	. Novel extended multivariate public key cryptosystem [J]. Journal on Communications, 2014, 35(4): 17-154.
[3]	Shuai-ting QIAO,Yi-fa LI,Wen-bao HAN. Novel extended multivariate public key cryptosystem [J]. Journal on Communications, 2014, 35(4): 148-154.
[4]	Ke-hui WU,Xin-jie ZHAO,Tao WANG,Shi-ze GUO,Hui-ying LIU. Algebraic fault attack on PRESENT [J]. Journal on Communications, 2012, 33(8): 85-92.
[5]	Wen-ping GUO,Jin-liang AN. Performance research of the T′ algorithm over GF(2) [J]. Journal on Communications, 2011, 32(9): 82-87.
[6]	HANGLong Z,UWen-ling W,ENQiao-yan W. Review of algebraic attacks on stream ciphers [J]. Journal on Communications, 2006, 27(1): 91-98.