La répartition des fonctions qui s'écrivent comme somme de deux bijections est fondamentale en cryptographie. Deux conjectures se distinguent :
- une fonction pouvant s'écrire comme somme de deux bijections, peut s'écrire d'un nombre de façon différentes au moins égal à la moyenne des combinaisons possibles de deux bijections.
- Le nombre minimum de combinaisons de deux bijections pour une fonction donnée est atteint pour une bijection.
La démonstration de l'une ou l'autre de ces conjectures est un objectif majeur de la thèse.
Ces propriétés permettent d'assurer des preuves de sécurité dans de nombreux schémas. La fonction CRUNCH par exemple est basée sur ce schéma. On pourrait bien sûr utiliser ce schéma pour d'autres fonctions de hachage. Il est à noter que cela s'adapte particulièrement bien avec les récentes architectures des microprocesseurs (calculs en parallèle).
Ce thème a fait l'objet d'un exposé dans le cadre du séminaire jeune du département de mathématiques de Cergy-Pontoise, et également du mémoire de stage de mon Master.
Le NIST, National Institute of Standards and Technology (USA), a lancé un appel à candidature pour une nouvelle fonction de hachage. En effet, le standard SHA-1 est en passe de subir une attaque majeure. Il ne resterait plus alors que SHA-2 pour garantir la sécurité des échanges internationaux.
Dans ce cadre, j'ai participé activement au projet CRUNCH. Le design de la fonction est en grande partie due à Jacques Patarin. J'ai ensuite été chargé de la programmation et de la finalisation de la fonction. Une équipe d'une dizaine de personnes s'est formée autour de ce projet, car plusieurs domaines de recherche étaient impliqués. J'ai coordonné les différents travaux, et finalement notre fonction a été acceptée par le NIST. Le NIST a reçu 64 projets et en a retenu 51. Parmi les 51, une douzaine ont déjà subi de sérieuses attaques qui les mettent hors compétition. J'ai également présenté ce projet lors d'une conférence organisée par le NIST à Leuvens en Belgique.
Le zero knowledge est un concept récent qui permet l'authentification sans divulgation du secret. Différents articles présentent des protocoles d'authentification en utilisant ce principe. Mon travail de recherche consiste à trouver de nouveaux protocoles, et à unifier les différents protocoles existants.
Avec Valérie Nachef et Jacques Patarin nous travaillons actuellement sur plusieurs variantes de problèmes zéro-knowledge. Les deux pistes principales étant le problème MP généralisé, en lien avec la multiplication des matrices, et le problème du Rubik's Cube, lorsque le nombre de permutations autorisées est fixé. Ce travail va sans doute conduire à la rédaction d'un nouvel article d'ici la fin de l'année 2011.
Grâce à une génération systématique de toutes les attaques rectangles pour un nombre de division du message plus petit que 7, j'ai pu améliorer et corriger les meilleures attaques connues sur ce genre de schémas. Mon programme a pu déceler des problèmes dans certaines attaques dus à une sorte de goulot d'étranglement des variables. Ce genre de problème est très difficile à voir directement. Avec Valérie Nachef, nous avons pu généraliser les attaques trouvées pour obtenir une classification complète et utile pour d'autres travaux. Notre article a été accepté à la conférence ASIACRYPT 2010. J'ai été présenter notre article à la conférence de Singapour en décembre 2010.
Les calculs de variances sont à chaque fois nécessaires pour trouver les meilleures attaques génériques sur un grand nombre de schémas. Pour l'instant ces calculs assez complexes sont fait à la main. J'espère automatiser une grande partie de ces calculs, ce qui pourra nous permettre de trouver de nouvelles attaques, et peut être même de construire des schémas plus solides.
Les équations de Brent sont liés à l'optimisation du calcul du produit de deux matrices. Il est prouvé que pour deux matrices 2x2, le nombre minimum de multiplications nécessaires pour multiplier les deux matrices est égal à 7. Ce résultat, du à Strassen, date des années 70. Pour le produit de deux matrices carrées 3x3, le résultat reste ouvert. On sait que le nombre minimum de multiplications est compris entre 19 et 23 (au lieu de 27). Je suis en train d'écrire un algorithme pour chercher des solutions pour 21 ou 22 multiplications.
|
