Cryptanalysis of Two New Instances of TTM Cryptosystem

Xuyun Nie School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China; State Key Laboratory of Information Security Graduate School of Chinese Academy of Sciences Beijing 100049, China Xin Jiang State Key Laboratory of Information Security Graduate School of Chinese Academy of Sciences Beijing 100049, China Lei Hu State Key Laboratory of Information Security Graduate School of Chinese Academy of Sciences Beijing 100049, China Jintai Ding Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH, 45220, USA

TBD mathscidoc:2207.43023

IACR Cryptology ePrint Archive, 381, 2007.9
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} 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.
No keywords uploaded!
[ Download ] [ 2022-07-11 12:15:51 uploaded by dingjt ] [ 284 downloads ] [ 0 comments ]
@inproceedings{xuyun2007cryptanalysis,
  title={Cryptanalysis of Two New Instances of TTM Cryptosystem},
  author={Xuyun Nie, Xin Jiang, Lei Hu, and Jintai Ding},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220711121551938878600},
  booktitle={IACR Cryptology ePrint Archive},
  pages={381},
  year={2007},
}
Xuyun Nie, Xin Jiang, Lei Hu, and Jintai Ding. Cryptanalysis of Two New Instances of TTM Cryptosystem. 2007. In IACR Cryptology ePrint Archive. pp.381. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220711121551938878600.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved