In this talk, we will focus our attention to a general technique for
evaluating the
security of cryptographic primitives, the so-called algebraic
cryptanalysis.
The basic idea is to model a cryptographic primitive as a
set of algebraic equations. The system is constructed in such a way as to
have a correspondence between the solutions of this system, and a secret
information of the considered primitive. Once this modeling is done, the
problem is then to solve the algebraic system (or to evaluate the
difficulty of solving such a system). Up to now, Gröbner bases appear to
yield the best algorithms to do so.
Dans le cas des entiers modulo ou dans des extensions de cardinalité très inférieure au plus grand entier ou flottant machine, nous proposons de stocker plusieurs éléments dans un même mot machine. Sous certaines conditions explicitées dans cet exposé cela permet d'effectuer une multiplication de polynômes de petits degrés extrêmement rapide. Nous montrons comment utiliser cette routine, combinée à un nouvel algorithme pour réduire simultanément plusieurs entiers modulo, pour faire de l'arithmétique polynomiale générale et de l'algèbre linéaire haute performance.
Les équations différentielles ou aux différences linéaires à
coefficients polynomiaux
constituent des structures de données adéquates pour représenter et
manipuler efficacement leurs fonctions ou suites solutions (dites
différentiellement
finies ou holonomes). L'objet de cet exposé est de montrer comment
majorer automatiquement une suite de complexes donnée par une récurrence
linéaire à coefficients polynomiaux par une suite n simple z à valeurs
positives.
Les majorations obtenues sont fines, au sens où les suites majorantes ont
(sous des hypothèses convenables) le même ordre de croissance asymptotique
que les solutions qu'elles majorent. Elles peuvent être évaluées
efficacement,
et admettent généralement des formes closes simples. Il s'agit d'un travail
en cours avec mon directeur de thèse Bruno Salvy, à partir notamment des
travaux de Joris van der Hoeven sur la méthode de Cauchy-Kovalevskaïa en
analyse effective.
Appliqué aux coefficients ou aux restes de la série de Taylor d'une fonction
différentiellement finie, ce procédé de calcul de bornes permet de
déterminer
à quel ordre tronquer la série pour garantir une certaine borne d'erreur sur
la somme. La série tronquée peut être utilisée pour évaluer numériquement à
grande précision la fonction ; la finesse des bornes se reflète alors
sur la complexité
de l'algorithme d'évaluation. J'évoquerai l'implémentation de ces
algorithmes
en présentant un module Maple (à l'état de prototype) qui fournit
des fonctionnalités d'évaluation efficace et garantie des fonctions
holonomes
s'appuyant sur une version de l'algorithme de calcul de bornes décrit.
