Cryptanalysis of dragon scheme

doi:10.1016/S1005-8885(09)60492-1

中国邮电高校学报(英文) ›› 2010, Vol. 17 ›› Issue (4): 80-87.doi: 10.1016/S1005-8885(09)60492-1

• Artificial Intelligence • 上一篇下一篇

Cryptanalysis of dragon scheme

袁峰¹,胡予濮¹,王艳², 欧海文³

1. 西安电子科技大学计算机网络与信息安全教育部重点实验室
2. 西安建筑科技大学理学院
3. 北京电子科技学院

收稿日期:2010-04-09 修回日期:2010-07-13 出版日期:2010-08-30 发布日期:2010-08-31
通讯作者: 袁峰 E-mail:fyuan1234@yahoo.cn
基金资助:
This work was supported by the National Natural Science Foundation of China (60970119,60803149), the Youth Science and Technology Foundation of Xi’an University of Architecture and Technology (QN0831), and the National Basic Research Program of China (2007CB311201).

Cryptanalysis of dragon scheme

YUAN Feng, HU Yu-pu, WANG Yan, OU Hai-wen

Key Laboratory of Computer Networks and Information Security, Ministry of Education, Xidian University, Xi’an 710071, China

Received:2010-04-09 Revised:2010-07-13 Online:2010-08-30 Published:2010-08-31
Supported by:
This work was supported by the National Natural Science Foundation of China (60970119,60803149), the Youth Science and Technology Foundation of Xi’an University of Architecture and Technology (QN0831), and the National Basic Research Program of China (2007CB311201).

摘要/Abstract

摘要：

Patarin proposed the dragon scheme, pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function. This paper presents an algebraic method to attack the candidate dragon signature algorithm. The attack borrows the basic idea of the attack due to Kipnis and Shamir, and utilizes the underlying algebraic structure of the candidate dragon signature algorithm over the extension field to derive a way to enable the variable Y be viewed as a fixed value. The attack recovers the private keys efficiently when the parameters are and

关键词:

cryptography, public key cryptography, polynomials, mapping, multivariate, dragon scheme, algebraic method, cryptanalysis

Abstract:

Key words:

cryptography, public key cryptography, polynomials, mapping, multivariate, dragon scheme, algebraic method, cryptanalysis

YUAN Feng, HU Yu-pu, WANG Yan, OU Hai-wen. Cryptanalysis of dragon scheme[J]. Acta Metallurgica Sinica(English letters), 2010, 17(4): 80-87.

参考文献

1. Mu N B, Hu Y P, Ou H W. Broadcast encryption schemes based on RSA. The Journal of China Universities of Posts and Telecommunications, 2009, 16 (1): 69-75

2. Ding J, Gower J E, Schmidt D S. Multivariate public key cryptosystems. New York, NY, USA: Springer, 2006: 2-3

3. Matsumoto T, Imai H. Public quadratic polynominal-tuples for efficient signature-verification and message-encryption. Advances in Cryptology: Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (Eurocrypt’88), May 25-27, 1988, Davos, Switzerland. LNCS 330. Berlin, Germany: Springer-Verlag, 1988: 419-453

4. Patarin J. Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt’88. Advances in Cryptology: Proceedings of the 15th Annual International Cryptology Conference (Crypto’95), Aug 27-31, 1995, Santa Barbara, CA, USA. LNCS 963. Berlin, Germany: Springer-Verlag, 1995: 248-261

5. Patarin J. Hidden field equations (HFE) and isomorphism of polynomials (IP): Two new families of asymmetric algorithms. Advances in Cryptology: Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (Eurocrypt’96), May 12-16, 1996, Saragossa, Spain. LNCS 1070. Berlin, Germany: Springer-Verlag, 1996: 33-48

6. Patarin J. Asymmetric cryptography with a hidden monomial. Advances in cryptology:Proceedings of the 16th Annual International Cryptology Conference (Crypto’96), Aug 18-22,1996, Santa Barbara, CA, USA. LNCS 1109. Berlin, Germany: Springer-Verlag, 1996: 45-60

7. Kipnis A, Shamir A. Cryptanalysis of the HFE public key cryptosystem by relinearization. Advances in Cryptology: Proceedings of the 19th Annual International Cryptology Conference (Crypto’99), Aug 15-19, 1999, Santa Barbara, CA, USA. LNCS 1666. Berlin, Germany: Springer-Verlag, 1999: 19-30

8. Goubin L, Courtois N. Cryptanalysis of the TTM cryptosystem. Advances in cryptology: Proceeding of International Conference on the Theory and Applications of Cryptologic Techniques(Asiacrypt’00), Dec 3-7, 2000, Kyoto, Japan. LNCS 1976. Berlin, Germany: Springer-Verlag, 2000: 44-57

9. Courtois N. The security of hidden field equations (HFE). Topics in cryptology: Proceedings of Topics in Cryptology (CT-RSA’01), Apr 8-12, 2001, San Francisco, CA, USA. LNCS 2020. Berlin, Germany: Springer-Verlag, 2001: 266-281

10. Coppersmith D, Stern J, Vaudenay S. The security of the birational permutation signature schemes. Journal of Cryptology, 1997, 10(3): 207-221

11. Faugère J C, Vehel F L, Perret L. Cryptanalysis of MinRank. Advances in Crytography:Proceedings of the 28th Annual International Cryptology Conference (Crypto’08), Aug 17-21, 2008, Santa Barbara, CA, USA. LNCS 5157. Berlin, Germany: Springer-Verlag, 2008: 280-296

12. Courtois N. Efficient zero-knowledge authentication based on a linear algebra problem MinRank. Advances in Cryptology: Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt’01), Dec 9-13, 2001, Gold Coast, Australia. LNCS 2248. Berlin, Germany: Springer-Verlag, 2001: 402-421

Cryptanalysis of dragon scheme

Cryptanalysis of dragon scheme

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价