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

*T.Moh and 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}$).

**Category / Keywords: **public-key,TTM

**Date: **received 13 Jul 2004, last revised 26 Jul 2004

**Contact author: **ttm at math purdue edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20040726:185149 (All versions of this report)

**Short URL: **ia.cr/2004/168

[ Cryptology ePrint archive ]