Equipe Algèbre, Géométrie, Combinatoire et applications à la Cryptographie et au Codage
Responsable de l’équipe : Sihem Mesnager
**************************************************************************
Les thèmes de recherche de l’équipe AGC3 « Algèbre, Géométrie, Combinatoire et applications à la Cryptographie et au Codage » se rattachent à l’algèbre et à la géométrie entendues dans leur sens le plus large avec interaction avec la combinatoire et les applications à la protection de l’information (cryptographie et codage). En plus des sujets traditionnellement représentés à Paris VIII — tels que les mathématiques discrètes (l’étude des fonctions booléennes, des fonctions vectorielles et d’autres structures discrètes pour la cryptographie symétrique et la théorie des codes correcteurs), la combinatoire additive et le codage algébrique — y figurent aussi l’arithmétique, la géométrie algébrique, la géométrie discrète, liées à la cryptographie et le codage, et l’algorithmique. L’équipe AGC3 attache également une importance aux applications contemporaines et aux retombées industrielles, en particulier celles liées à la cryptographie et au codage, que celles-ci soient le fait de ses membres (en collaboration avec des entreprises), ou celui d’entreprises utilisant seules les avancées en recherche de ses membres en algèbre, géométrie et combinatoire.
Ci-dessous une brève description des activités de recherche des membres permanents et émérites de l’équipe AGC3.
1. Martino Borello (lien: https://www.math.univ-paris13.fr/~borello/) travaille principalement dans le domaine de la théorie des codes algébrique. Plusieurs de ses articles traitent des codes autoduaux et de leurs automorphismes, avec une attention particulière pour les codes extrémals. Plus récemment, ses recherches ont porté sur deux familles de codes linéaires, à savoir les G-codes (qui sont des codes quasi-cycliques avec d’autres symétries) et les codes minimaux. Les deux familles présentent des liens intéressants avec d’autres domaines des mathématiques, tels que la théorie des représentations, la géométrie finie et la combinatoire, ainsi que des applications possibles en cryptographie. Au cours de sa carrière universitaire, il s’est également intéressé à des problèmes sur les réseaux euclidiens, la fonction de Möbius des sous-groupes et l’arithmétique des corps finis.
2. Claude Carlet (lien: https://www.math.univ-paris13.fr/~carlet/) a, tout au long de sa carrière, réalisé seul et en collaboration une étude fondamentale des fonctions booléennes pour les chiffrements par flots, qu’il s’agisse des schémas classiques ou de ceux destinés à une utilisation hybride avec un chiffrement totalement homomorphe (FHE). Il a ouvert de nouvelles voies dans plusieurs directions de recherche (sur la non-linéarité d’ordre supérieur, l’immunité algébrique, les fonctions partiellement courbes et leurs généralisations.
Il a introduit de nombreuses constructions de fonctions booléennes pour les chiffrements par flots ou pour une utilisation dans des contre-mesures aux attaques par canaux auxiliaires. Citons par exemple la construction connue sous le nom de fonction de Carlet-Feng, qui a en quelque sorte «sauvé de l’extinction» les chiffrements par flots utilisant des fonctions booléennes comme principaux composants non linéaires (lors de la parution de son article présenté à Asiacrypt 2008, cinq ans après l’introduction des attaques algébriques par Courtois et Meier, il n’y avait pas de fonction booléenne connue utilisable dans les chiffrements par flots et permettant de résister à toutes les attaques, y compris les attaques algébriques et algébriques rapides). Depuis 2008, aucune nouvelle idée n’a été trouvée conduisant à des alternatives significativement différentes.
Il a mené seul et en collaboration des études fondamentales sur les boites de substitution pour les chiffrements par blocs. Par exemple, il a fallu 25 ans avant que la caractérisation par la transformée de Walsh des fonctions presque parfaitement non linéaires (APN) (obtenue par Chabaud et Vaudenay en 1994) soit généralisée par lui aux fonctions différentiellement uniformes. Ces nouveaux résultat ont conduit à de nouvelles notions et de nouvelles propriétés. Il a également étudié les fonctions plateaux vectorielles, en relation avec la presque parfaite nonlinéarité.
Il a contribué à la découverte de plusieurs classes infinies de fonctions APN et de fonctions différentiellement uniformes. Il a introduit une toute nouvelle construction de fonctions APN, dites bivariées, suite à laquelle ont été trouvées une majorité des constructions récentes.
Récemment, il a introduit une manière efficace d’étudier le degré algébrique des fonctions vectorielles et en particulier des fonctions composites, au moyen des indicatrices de leurs graphes; cela lui a permis de clarifier les bornes connues (qui supposent toutes des propriétés des fonctions considérées) et d’obtenir la première borne efficace qui soit valable pour toutes les fonctions sans aucune condition.
Il a participé à la conception de cryptosystèmes. Par exemple, FLIP, présenté à EuroCrypt 2016, est un chiffrement par flots destiné à être utilisé de manière hybride avec du chiffrement FHE, et à avoir des applications à la sécurité dans le cloud; et PICARO est un chiffrement par blocs conçu pour minimiser le coût des contre-mesures contre les attaques par canaux auxiliaires.
Il a également collaboré à la cryptanalyse des chiffrements par flots.
Sur un plan de recherche plus applicative et industrielle, il a beaucoup travaillé sur les attaques par canaux auxiliaires (SCA) et les attaques par injection de faute (FIA), et sur les contre-mesures de masquage à leur encontre. Ces études ont donné lieu à de nouvelles notions telles que les paires de codes complémentaires, et renouvelé l’intérêt de plusieurs notions connues, telles que celle des fonctions sans corrélation de poids faibles et les codes LCD, dont les applications à la résistance contre les SCA et les FIA sont tout à fait essentielles.
3. Les recherches de Julien Lavauzelle (lien :
https://www.math.univ-paris13.fr/~lavauzelle/index.html) s’inscrivent
dans le domaine des codes correcteurs et leur application en
cryptographie. Il s’intéresse notamment à la construction de codes à
propriétés locales, par des méthodes algébriques, géométriques ou
combinatoires. Les applications concernées sont, par exemple, le retrait
confidentiel d’information (PIR), les preuves d’extraction ou le
chiffrement.
4. Les travaux de Sihem Mesnager (lien: https://www.math.univ-paris13.fr/~mesnager/) se situent en mathématiques appliquées à la protection de l’information: cryptographie symétrique et codage. Certains de ses travaux actuels en mathématiques pour la cryptographie portent sur l’étude algébrique (existence, caractérisation, construction, classification, énumération, etc) de fonctions définies sur un corps fini (sous tous leurs aspects : booléennes, vectorielles, p- aires (où $p$ est un nombre premier) et généralisées (dont le co-domaine est l’anneau des entiers modulo une puissance d’un nombre premier) ayant des propriétés cryptographiques (résilience, non-linéarité, l’immunité algébrique, etc). Parmi ces fonctions, on cite les fonctions hautement non-linéaires (qui sont des fonctions sont d’une importance essentielle en cryptographie symétrique pour éviter certaines attaques fondamentales comme la cryptanalyse linéaire), ses sous classes (comme les fonctions hyper-courbes) et ses sur-classes (comme les fonctions plateaux). Elle a introduit des nouvelles méthodes algébriques pour l’étude de toutes ces familles de fonctions et utilisé à fois la théorie de Galois et des éléments de la théorie algébrique des nombres. Elle a aussi travaillé sur des objets algébriques faisant intervenir des polynômes sur des corps finis tels que les permutations polynomiales, les involutions, les fonctions 2-en-1, les polynômes de Dickson, les o-polynômes et les polynômes de Müller–Cohen–Matthews, pouvant jouer un rôle important en cryptographie symétrique. Elle a résolu et participé à la résolution de plusieurs conjectures (certaines date de plus de 30 ans) et a résolu des problèmes liés a la cryptographie homomorphique (amélioration de la borne supérieure des fonctions restreintes dans le cadre du cryptosystème FLIP, constructions de fonctions WPB [Weighwise Perfectly Balanced]).
Dans les problèmes algébriques liés au codage, elle a travaillé sur un certain nombre de codes tels que les codes de Reed-Muller, les codes LRC (qui jouent un rôle dans les problèmes de stockage de données rencontrés par des entreprises telles que Google et pour des utilisateurs comme pour Dropbox et Facebook), les codes MDS, les codes LCD (qui sont au centre d’une nouvelle technique pour contre-carrer les attaques par canaux cachés sur les implémentations cryptographiques), les codes définis à partir de fonctions définies sur des corps finis, les code minimaux (pour le partage du secret et le calcul « deuxpatite » sécurisé), etc.
Dans ses travaux, elle utilise la théorie des corps finis, la transformation de Fourier discrète, des sommes exponentielles, des outils de l’arithmétique et de la théorie des nombres, des courbes algébriques et des objets de la géométrie finie.
5. Les recherches de Wolfgang Schmid (lien: https://www.math.univ-paris13.fr/~schmid/personal/index.html) portent sur la combinatoire additive et sur des questions liées aux factorisations. Ses recherches en combinatoire additive concernent les suites à somme nulle dans les groupes abéliens finis (par exemple, la constante de Davenport, la constante de Harborth, la constante d’ Erdős-Ginzburg-Ziv et les problèmes inverses associés). Ses recherches sur les factorisations concernent principalement la classification des phénomènes arithmétiques dans les anneaux de Dedekind, et plus généralement les monoïdes de Krull.
**************************************************************************