Paper 2004/168

Building Instances of TTM Immune to the Goubin-Courtois Attack and the Ding-Schmidt Attack

T. Moh, J. M. Chen, and Boyin Yang

Abstract

We think that there are two main attacks on TTM cryptosystem; the Goubin-Courtois attack ([6]) and the Ding-Schmidt attack ([5]). The paper of Goubin-Courtois is not clearly written. Their arguments (with many gaps) depend on an parameter $r$ which is never defined. It is nature to take their parameter $r$ to be the index $s$ used in our "lock polynomials" (see section 1). Later on Courtois implies otherwise in his website. In their paper ([6]) or in his website, Courtois simply declares that TTM is of rank 2 (i.e., $r=2$) without any justification. In this paper, we will illustrate another example (cf Example below) satisfies both requirements, i.e., the index $s$ used in our "lock polynomials" (see section 1) is 7, and the number of variables in all quartic forms is 4 which shows that Goubin-Courtois' unsubstantial claim: "TTM is rank 2" invalid. Thus we settle this question of Goubin-Courtois attack once for all. To guard against "high rank attack", in this Example every variable appears 9 times in 9 different polynomials. On the other hand J.~Ding and D.~Schmidt show ([5]) how to construct an interesting attack on some implementations of TTM ([10,11]) based on Patarin's idea ([14]) of bilinear relations created by the structure in the kernel equations in an implementation of TTM. The success of this attack is accidental. In our Example, the attack fails. we will describe a {\it mixed implementation} which will make any attack, which is sensitive to the size of the ground field, ineffective. In this paper, the Example is strong (i.e., $\geq 2^{148})$ against both Goubin-Courtois attack and Ding-Schmidt attack as well as other previously proposed incomplete attacks like XL($>2^{97}$), FXL($>2^{112}$).