Identifiant pérenne de la notice : 226506479
Notice de type
Notice de regroupement
Note publique d'information : Depuis ces dix dernières années, les attaques algébriques sur lelogarithme discret
sur les courbes elliptiques (ECDLP) connaissent unlarge succès. C'est dans ce contexte
que s'inscrit cette thèse dontles enjeux sont doubles.D'une part, nous présentons
de nouveaux outils de cryptanalysealgébrique c'est à dire de nouveaux algorithmes
de résolution desystèmes polynomiaux. Dans un premier temps, nous étudions lessystèmes
avec symétries. Nous montrons que la résolution de telssystèmes est étroitement liée
à la résolution de systèmesquasi-homogènes et proposons ainsi de nouveaux résultats
decomplexité. Dans un second temps, nous nous intéressons à l'étapebloquante de la
résolution de systèmes par bases de Gröbner : lechangement d'ordre. La complexité
classique de cette étape est cubiqueen le nombre de solutions. Nous proposons pour
la première foisdes algorithmes de changement d'ordre de complexité sous-cubique en
lenombre de solutions.D'autre part, nous étudions la résolution du problème de décompositionde
points (PDP) sous-jacent aux attaques algébriques du ECDLP. Nousmettons en évidence
des familles de courbes elliptiques possédant dessymétries particulières. Ces symétries
impliquent un gain exponentielsur la complexité de la résolution du PDP. La modélisation
du PDP sousforme de systèmes polynomiaux nécessite le calcul des polynômes deSemaev.
Les symétries des courbes binaires nous permettent d'élaborerun nouvel algorithme
par évaluation interpolation pour le calcul de cespolynômes. Muni de cet algorithme
nous établissons unnouveau record de calcul de polynômes de Semaev.
Note publique d'information : Since the last decade, algebraic attacks on the elliptic curvediscrete logarithm problem
(ECDLP) are successful. This thesis takesplace in this context and its main stakes
are twofold. On the one hand, we present new tools for algebraic cryptanalysis thatis
to say new algorithms for polynomial systems solving. First, weinvestigate polynomial
systems with symetries. We show that solvingsuch a system is closely related to solve
quasi-homogeneous systemsand thus we propose new complexity bounds. Then, we study
thebottleneck of solving polynomial systems with Gröbner bases: change ofordering
algorithms. The usual complexity for such algorithms is cubicin the number of solutions.
For the first time, we propose new changeof ordering algorithms with sub-cubic complexity
in the number ofsolutions.On the other hand, we investigate the point decomposition
probleminvolved in algebraic attacks on the ECDLP. We highlight some familiesof elliptic
curves that admit particular symmetries. These symmetriesimply an exponential gain
on the complexity of solving the pointdecomposition problem. The modelling of this
problem requires tocompute Semaev summation polynomials. The symmetries of binary
curvesallow us to propose a new algorithm to compute summationpolynomials. Equipped
with this algorithm we establish a new record onthe computation of these polynomials.
paprika.idref.fr
data.idref.fr
Documentation
