Breaking a New Instance of TTM Cryptosystems

Xuyun Nie 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 Jianyu Li State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijing, 100049, China Crystal Updegrove Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH, 45220, USA Jintai Ding Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH, 45220, USA

TBD mathscidoc:2207.43025

ACNS 2006, 210–225, 2006.6
In 2004, the inventors of TTM cryptosystems proposed a new scheme that could resist the existing attacks, in particular, the Goubin-Courtois attack [GC00] and the Ding-Schmidt attack [DS03]. In this paper, we show the new version is still insecure, and we find that the polynomial components of the cipher (F_i) satisfy nontrivial equations of the special form ∑_{i=0}^{n−1} a_i x_i + ∑_{0≤j≤k≤m−1} b_{jk} F_j F_k + ∑_{j=0}^{m−1} c_j F_j + d = 0, which could be found with 2^{38} computations. From these equations and consequently the linear equations we derive from these equations for any given ciphertext, we can eliminate some of the variables x_i by restricting the functions to an affine subspace, such that, on this subspace, we can trivialize the "lock" polynomials, which are the key structure to ensure its security in this new instance of TTM. Then with method similar to Ding-Schmidt [DS03], we can find the corresponding plaintext for any given ciphertext. The total computational complexity of the attack is less than 2^{39} operations over a finite field of size 2^8. Our results are further confirmed by computer experiments.
No keywords uploaded!
[ Download ] [ 2022-07-11 12:33:37 uploaded by dingjt ] [ 308 downloads ] [ 0 comments ]
@inproceedings{xuyun2006breaking,
  title={Breaking a New Instance of TTM Cryptosystems},
  author={Xuyun Nie, Lei Hu, Jianyu Li, Crystal Updegrove, and Jintai Ding},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220711123337253295602},
  booktitle={ACNS 2006},
  pages={210–225},
  year={2006},
}
Xuyun Nie, Lei Hu, Jianyu Li, Crystal Updegrove, and Jintai Ding. Breaking a New Instance of TTM Cryptosystems. 2006. In ACNS 2006. pp.210–225. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220711123337253295602.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved