Cryptanalysis of the TRMS Signature Scheme of PKC’05
作者： Luk Bettale , Jean-Charles Faugère , Ludovic Perret
DOI: 10.1007/978-3-540-68164-9_10
关键词:
摘要: In this paper, we investigate the security of Tractable Rationale Maps Signature (TRMS) signature scheme [9] proposed at PKC'05. To do so, present a hybrid approach for solving algebraic systems naturally arising when mounting signature-forgery attack. The basic idea is to compute Grobner bases several modified rather than basis initial system. We have been able provide precise bound on (worst-case) complexity approach. For that, however assumed technical condition in our attack; namely are semi-regular [3,5]. This claim supported by experimental evidences. Finally, it turns out that efficient. obtained bounded from above 257 forge parameters designers TRMS [9]. can be improved; assuming an access 216 processors (which very reasonable), one actually approximately 51 hours.
springer.com
archives-ouvertes.fr
springerlink.com
unicaen.fr 参考文章(53)
Jean-Charles Faugère, Antoine Joux, Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases Advances in Cryptology - CRYPTO 2003. ,vol. 2729, pp. 44- 60 ,(2003) , 10.1007/978-3-540-45146-4_3
Bo-Yin Yang, Jiun-Ming Chen, Nicolas T. Courtois, On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis international conference on information and communication security. pp. 401- 413 ,(2004) , 10.1007/978-3-540-30191-2_31
Jean-Charles Faugére, A new efficient algorithm for computing Gröbner bases (F4) Journal of Pure and Applied Algebra. ,vol. 139, pp. 61- 88 ,(1999) , 10.1016/S0022-4049(99)00005-5
Bruno Salvy, Magali Bardet, Jean-Charles Faugère, On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations International Conference on Polynomial System Solving. pp. 71- 75 ,(2004)
Jean-Charles Faugère, Ludovic Perret, Cryptanalysis of 2R− Schemes Lecture Notes in Computer Science. ,vol. 4117, pp. 357- 372 ,(2006) , 10.1007/11818175_21
Whitfield Diffie, Martin E Hellman, None, New Directions in Cryptography IEEE Transactions on Information Theory. ,vol. 22, pp. 644- 654 ,(1976) , 10.1109/TIT.1976.1055638
Fei-Hwang Chang, Lih-Chung Wang, Revision of Tractable Rational Map Cryptosystem. IACR Cryptology ePrint Archive. ,vol. 2004, pp. 46- ,(2004)
Serge Vaudenay, Advances in Cryptology - Eurocrypt 2006 ,(2008)
Advances in Cryptology - CRYPTO 2007 Springer Berlin Heidelberg. ,(2007) , 10.1007/978-3-540-74143-5
Advances in Cryptology - CRYPTO 2003 Springer Berlin Heidelberg. ,(2003) , 10.1007/B11817