You are looking at a specific version 20070927:044106 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
multivariate public key cryptosystemTTMalgebraic attacklinearization equationtriangular cryptosystem.
Contact author(s)
nxy7509 @ sohu com
History
2007-09-27: received
Short URL
https://ia.cr/2007/381
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.