Welcome to the resource topic for 2004/168
Title:
Building Instances of TTM Immune to the Goubin-Courtois Attack and the Ding-Schmidt Attack
Authors: T. Moh, J. M. Chen, 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}).
ePrint: https://eprint.iacr.org/2004/168
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .