[Resource Topic] 2007/381: Cryptanalysis of Two New Instances of TTM Cryptosystem

Welcome to the resource topic for 2007/381

Cryptanalysis of Two New Instances of TTM Cryptosystem

Authors: Xuyun Nie, Xin Jiang, Lei Hu, Jintai Ding


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.

ePrint: https://eprint.iacr.org/2007/381

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .