Étude de la Sécurité de Schémas de Chiffrement par Bloc et de Schémas Multivariés

Thèse soutenue par Joana Treger du laboratoire cryptographie et composants de l'ANSSI le lundi 28 juin 2010.

Jury :
- Jean-Sébastien Coron - Univ. Luxembourg
- Pierre-Alain Fouque - ENS
- Henri Gilbert - Orange Labs (Rapporteur)
- Eliane Jaulmes - ANSSI
- Antoine Joux - UVSQ & DGA
- David Naccache - Univ. Paris II & ENS (Rapporteur)
- Jacques Patarin - UVSQ (Directeur)

La thèse se concentre sur l'étude de la sécurité de schémas de chiffrement par blocs, et de schémas multivariés.

Dans la première partie de la thèse, nous nous intéressons à l'étude de schémas de chiffrement par blocs, notamment les schémas de Feistel
avec permutations internes et les schémas du type Misty. Le cadre de l'étude est générique, i.e. les permutations internes sont supposées
aléatoires. Ceci permet d'obtenir des propriétés de la structure même des schémas, sans prendre en compte leur contexte d'utilisation.
Cette partie se concentre sur les attaques génériques sur ces deux schémas.

La deuxième partie de la thèse concerne l'étude de cryptosystèmes multivariés. Une propriété de la différentielle de la clé publique
du schéma HM est exhibée, fournissant un distingueur. Par ailleurs, une attaque par bases de Gröbner permet d'inverser le système
efficacement. Nous exposons également une attaque sur le schéma HFE, permettant le recouvrement de la clé privée pour une famille d'instances
particulières, classées à présent comme "clés faibles". La complexité de cette attaque se ramène à la résolution d'une instance du problème IP.