Cryptology ePrint Archive: Report 2007/381

Cryptanalysis of Two New Instances of TTM Cryptosystem

Xuyun Nie and Xin Jiang and Lei Hu and Jintai Ding

Abstract: In 2006, Nie et al proposed an attack to break an instance of TTM cryptosystems. However, the inventor of TTM disputed this attack and he proposed two new instances of TTM to support his viewpoint. At this time, he did not give the detail of key construction --- the construction of the lock polynomials in these instances which would be used in decryption. The two instances are claimed to achieve a security of $2^{109}$ against Nie et al attack. In this paper, we show that these instances are both still insecure, and in fact, they do not achieve a better design in the sense that we can find a ciphertext-only attack utilizing the First Order Linearization Equations while for the previous version of TTM, only Second Order Linearization Equations can be used in the beginning stage of the previous attack. Different from previous attacks, we use an iterated linearization method to break these two instances. For any given valid ciphertext, we can find its corresponding plaintext within $2^{31}$ $\mathbb{F}_{2^8}$-computations after performing once for any public key a computation of complexity less than $2^{44}$. Our experiment result shows we have unlocked the lock polynomials after several iterations, though we do not know the detailed construction of lock polynomials.

Category / Keywords: public-key cryptography / multivariate public key cryptosystem, TTM, algebraic attack, linearization equation, triangular cryptosystem.

Date: received 25 Sep 2007

Contact author: nxy7509 at sohu com

Available format(s): PDF | BibTeX Citation

Version: 20070927:044106 (All versions of this report)

Short URL: ia.cr/2007/381

Discussion forum: Show discussion | Start new discussion