Breaking instance I of new TTM cryptosystems

TTM is a type of multivariate public key cryptosystem. In 2007, the inventor of TTM proposed two new instances of TTM to resist the existing attack, in particular, the Nie et al attack. The two instances are claimed to achieve a security of 2¹⁰⁹ against Nie et al attack. In this paper, we show that the instance I is still insecure, and in fact, it 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 the instances I. For any given valid ciphertext, we can find its corresponding plaintext within 2³¹ double-struck F₂₈-computations after performing once for any public key a computation of complexity less than 2⁴⁴. Our experiment result shows we have unlocked the lock polynomials after several iterations, though we do not know the detailed construction of lock polynomials.