Vous êtes ici : UVSQ RechercheDoctoratSoutenances de thèse

Vers une généralisation rigoureuse des Méthodes de Coppersmith pour la recherche de petites racines de polynômes

le 15 septembre 2008

Le lundi 15 septembre 2008 à 14h30

L'Université de Versailles Saint-Quentin-en-Yvelines UFR des Sciences - Bâtiment Descartes - Salle ARCHIMEDE (ancienne bibliotheque) 45 avenue des Etats-Unis - 78035 Versailles cedex

Madame Aurélie BAUER Spécialité : INFORMATIQUE Laboratoire : PRISM

«Vers une généralisation rigoureuse des Méthodes de Coppersmith

pour la recherche de petites racines de polynômes »

Présentée par : Aurélie Bauer

Résumé :

Les techniques de recherche de petites racines de polynômes par réduction de réseaux sont très largement utilisées dans les cryptanalyses de systèmes à clé publique. Dans le cas simple de polynômes univariés modulaires et bivariés sur les entiers, les méthodes de Coppersmith apportent une réponse rigoureuse. Pour un nombre de variables plus élevé, on utilise des généralisations multivariées de ces techniques.

 

Le résultat n'est alors garanti que sous une hypothèse d'indépendance algébrique entre polynômes. Cette hypothèse n'est pas considérée comme étant problématique puisqu'elle semble être souvent vérifiée en pratique. Cette thèse fournit, pour la première fois, un contre-exemple mettant en défaut l'hypothèse usuelle. Une construction est alors proposée dans le but de généraliser de façon rigoureuse les méthodes de Coppersmith. Les premières applications de cette construction à des exemples cryptographiques rééls fournissent des résultats prometteurs.

Mots clés : Robotique, Modélisation géométrique, Redondance, Comportement humain, Sous actionnement.

 Towar a rigorous generalization of Coppersmith's Methods for finding Small Roots of Multivariate Polynomial Equitations

 

                                              Author: Aurélie Bauer

Abstract : 

Methods for finding small roots of polynomial equations using lattice reduction are widely used in cryptanalysis of public-key cryptosystems. Coppersmith's methods give a rigorous answer in the univariate modular case and the bivariate one over the integers. A larger number of variables requires the use of multivariate generalization.

 

In these cases, the roots can finally be recovered under a well-known assumption concerning algebraic independence between polynomials. This assumption is not an issue as it seems to be often satisfied in practice. In this thesis, we highlight for the first time a counter example for which this well-known assumption always fails. As a consequence, we give a construction to make Coppersmith's metho
Informations complémentaires

Jean-Sébastien CORON, Professeur des Universités à l'Université du Luxembourg (Luxembourg) - Rapporteur

Arjen LENSTRA, Professeur des Universités à l'Ecole Polytechnique Fédérale de Lausanne (Suisse) - Rapporteur

Antoine JOUX, Professeur associé à l'Université de Versailles Saint-Quentin-en-Yvelines -Directeur de Thèse

Louis GOUBIN, Professeur des Universités à l'Université de Versailles Saint-Quentin-en-Yvelines -Examinateur

Jean-Charles FAUCHERE,  Directeur de recherche à l'Institut Nationale de Recherche en Informatique et en Automatique- Examinateur

Jacques STERN, Professeur des Universités à l'Ecole Normale Supérieure Paris - Examinateur

PHONG Q. Nguyen, Directeur de recherche à l'Institut National de Recherche en Informatique et en Automatique- Examinateur

Alexander MAY, Professeur Assistant à « Technische Universität Darmstadt (Allemagne) - Examinateur

Reynald LERCIER, Ingénieur Chef de l'Armement Habilité à Diriger des recherches - Examinateur (non présent à la soutenance)

Contact :
Service des Etudes Doctorales :