Vers une généralisation rigoureuse des méthodes de Coppersmith pour la recherche de petites racines de polynômes
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
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.
Abstract FR:
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 methods rigorous for multivariate polynomials. Its application to real-world cryptographic examples give promising results.