Françoise Levy-dit-Vehel

Codage pour le stockage distribué. Avec D. Augot, nous construisons et étudions les propriétés de codes localement décodables robustes et efficaces pour l'élaboration de protocoles de stockage/calcul distribué. Nous appliquons nos résultats aux preuves cryptographiques interactives (Preuves de récupérabilité, de possession...), et à la récupération confidentielle d'information.

Problèmes (combinatoires ou algébriques) donnant lieu à des chémas de type Polly Cracker. Avec Carlo Traverso, Téo Mora et Ludovic Perret, nous avons montré que ces schémas étaient tous vulnérables à des attaques algébriques, le plus souvent fondées sur des calculs de bases de Gröbner, mais pouvant également exploiter la forme du chiffré ou du procédé de chiffrement.

Problème du mot dans un monoïde ou dans un groupe. Il existe plusieurs tentatives de construction de schémas de chiffrement basés sur ce probllème. Avec Ludovic Perret, j'ai proposé des algorithmes de cryptanalyse de certains de ces schémas .  Nous avons aussi montré l'équivalence - du point de vue de la complexité des problèmes sous-jacents - de deux schémas, proposés resp. à Crypto'84 et Indocryt'03.

Décodage en métrique rang. A partir d'un travail dû à V. Ouvrivski et T. Johansson, j'ai proposé une modélisation du problème du décodage qui, couplée à une résolution par bases de Gröbner, permet d'obtenir de meilleurs résultats que les implantations existantes . Il est à noter que cette modélisation ne permet de résoudre le problème que pour des distance-rang minimales très petites. En d'autres termes, le décodage d'un code aléatoire en métrique rang reste difficile d'un point de vue pratique, même si les schémas basés sur ce problème sont pour la plupart vulnérables à des attaques structurelles.

Problème MinRank . Ce problème d'algèbre linéaire intervient à la fois en design et en cryptanalyse. Il est à la base de la construction d'un schéma d'identification ``zero-knowledge'' (dû à N. Courtois). Il sert aussi dans la cryptanalyse de HFE, de TTM et ses variantes, ou de Rainbow. Avec Jean-Charles Faugère et Ludovic Perret, j'ai proposé une modélisation de ce problème qui, en pratique, permet de casser les défis du système d'identification correspondants aux tailles de paramètres les plus praticables. Nous avons aussi mené une étude fine de la complexité théorique de notre attaque, donnant ainsi une borne polynomiale de complexité pour certaines tailles de paramètres, en particulier vérifiées pour ces défis.