Un compte rendu de la recherche effectuée par Piotr Graczyk et Patrice Sawyer sur la formule du produit sur les espaces symétriques. / CRSNG/NSERC

Nous donnons une description de l'anneau du groupe symétrique ZS_n <br />en tant que sous-anneau d'un produit direct d'anneaux de matrices sur Z,<br />utilisant le plongement de Wedderburn. Des morphismes modulaires<br />donnent des conditions nécessaires à un tuple de telles matrices pour<br />être contenu dans l'image de ZS_n. <br /><br />Résultat 1: Construction d'un système de morphismes modulaires donnant<br />une condition nécessaire et suffisante à un tel tuple.<br /><br />Résultat 2 : Une formule pour un morphisme modulaire de type<br />"décalage d'une case", ainsi précisant une partie d'un résultat de Carter <br />et Payne.

Ce mémoire vise à faire une synthèse sur la Schur positivité des différences de fonctions de Schur gauches. On cherche à voir la représentation de cet ensemble de fonctions à l'aide de la Schur positivité. Pour ce faire, on introduit premièrement les notions de base nécessaires à sa compréhension tel que les permutations, les partages, les diagrammes, les tableaux et les ensembles partiellement ordonnés. Ensuite une discussion sur l'algèbre graduée des fonctions symétriques s'impose puisque les fonctions de Schur forment une base des fonctions symétriques. On présente dans un deuxième temps certaines bases des fonctions symétriques. En fait, on voit la base des fonctions homogènes, la base des fonctions élémentaires et la base des fonctions monomiales. On voit par ailleurs la m-positivité qui est un autre ordre partiel semblable à la Schur positivité. En ce qui a trait aux fonctions de Schur gauches, on tente plus particulièrement de comprendre les égalités qui surviennent entre certaines fonctions de Schur gauches. On tente aussi de faire le point (en partie) sur les inégalités des coefficients de Littlewood-Richardson qui apparaissent lors d'un produit de fonctions de Schur ou lorsqu'on écrit les fonctions de Schur gauches en termes de fonctions de Schur. De plus, on veut trouver les seuls diagrammes gauches nécessaires à la représentation des ensembles partiellement ordonnés des fonctions de Schur gauches. Enfin, on vise à présenter certains ensembles partiellement ordonnés par la Schur positivité des fonctions de Schur gauches, de même qu'être en mesure de montrer l'existence d'un maximum d'arêtes liant les différents niveaux de la représentation de l'ensemble partiellement ordonné par la Schur positivité des fonctions de Schur gauches.

Nous nous proposons d'étudier les polynômes de Macdonald en les mettant en parallèle avec les polynômes orthogonaux classiques. En effet, ces deux types d'objets apparaissent comme fonctions propres d'opérateurs à significations physiques, les polynômes orthogonaux intervenant dans des situations décrites par une seule variable et les polynômes de Macdonald dans d'autres en demandant plusieurs. En développant chacune des deux théories, nous constaterons qu'elles s'élaborent de façon analogue. Notre but est ainsi de faire ressortir ces points communs tout en dégageant les différences entre les deux contextes. En mettant en lumière ce parallèle, nous constaterons toutefois qu'il manque un élément pour qu'il soit complet. En effet, les polynômes orthogonaux satisfont une récurrence à trois termes qui leur est caractéristique. Or rien d'analogue n'est présent dans la théorie des polynômes de Macdonald. Mais nous verrons qu'une conjecture portant sur une famille élargie de polynômes de Macdonald a été formulée qui permettrait de compléter le tableau. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : polynômes orthogonaux, fonctions symétriques, polynômes de Macdonald, conjecture n!.

Block ciphers are widely used building blocks for secure communication systems; their purpose is to ensure confidentiality of the data exchanged through such systems, while achieving high performance. In this context, a variety of aspects must be taken into account. Primarily, they must be secure. The security of a block cipher is usually assessed by testing its resistance against known attacks. However as attacks may exist that are currently unknown, generic security proofs are also tried to be obtained. On the other hand, another attack methodology is also worth considering. Contrary to the others, it aims at the implementation of the algorithm rather than the cipher itself. It is known as side-channel analysis. Finally, performance of a block cipher in terms of throughput is very important as well. More than any other cryptographic primitive, block ciphers allow a tradeoff to be made between security and performance. In this thesis, contributions are given regarding these various topics. In the first part of the thesis, we deal with two particular types of attacks, namely the square attack and key schedule cryptanalysis. We also consider security proofs in the so-called Luby-Rackoff model, which deals with adversaries having unbounded computation capabilities. More precisely, we are interested in the Misty structure, when the round functions are assumed to be involutions. The second part of the thesis is devoted to design and implementation aspects. First, we present a fault attack on substitution-permutation networks, which requires as few as two faulty ciphertexts to retrieve the key. We also study the security of DeKaRT, which is an algorithm intended to protect smart cards against probing attacks. Finally we present the design of ICEBERG, a block cipher deliberately oriented towards good performance in hardware, and give an adequate analysis of its security.

La théorie sur les polynômes de Macdonald a fait l'objet d'une quantité importante de recherches au cours des dernières années. Définis originellement par Macdonald comme une généralisation de quelques-unes des bases les plus importantes de l'anneau des fonctions symétriques, ces polynômes ont des applications dans des domaines tels que la théorie des représentations des groupes quantiques et physique des particules. Ce travail présente quelques-uns des résultats combinatoires les plus importants entourant ces polynômes, en mettant particulièrement l'accent sur la formule combinatoire prouvée récemment par Haglund, Haiman et Loehr pour les polynômes de Macdonald. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Polynômes de Macdonald, Fonctions symétriques, Combinatoire algébrique, Combinatoire énumérative, Théorie des représentations, Géométrie algébrique.

L'introduction des polynômes de Macdonald (Macdonald, 1988) comme des vecteurs propres associés à certains opérateurs reliés à la physique et comme une généralisation de quelques-unes des bases les plus importantes de l'anneau des fonctions symétriques, a donné lieu à un nombre remarquable de résultats dans divers domaines de l'algèbre, la combinatoire et la géométrie algébrique, entre autres. Ce travail présente un des liens entre la théorie des fonctions symétriques et la théorie des représentations des groupes, donné par les polynômes de Macdonald et les modules de Garsia-Haiman. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire algébrique, Combinatoire énumérative, Fonctions symétriques, Modules de Garsia-Haiman, Polynômes de Macdonald, Théorie des représentations.

Les travaux exposés dans ce document portent essentiellement sur l'étude des cryptanalyses statistiques des chiffrements par blocs. Certains des résultats présentés sont cependant suffisamment généraux pour pouvoir être utilisés dans d'autres contextes comme les chiffrements à flot, les attaques par canaux cachés, ... Après avoir donné quelques notions de base nécessaires à la compréhension du document, l'on s'intéresse aux deux grandes familles de cryptanalyses statistiques : les cryptanalyses linéaires et cryptanalyses différentielles. Un état de l'art est effectué afin de pouvoir appréhender les différentes problématiques liées à ces cryptanalyses. Dans un second temps, le document présente les travaux effectués durant ces trois années de thèse. Ceux-ci portent en majorité sur l'analyse de la complexité en données et de la probabilité de succès des cryptanalyses statistiques. Est aussi présenté un algorithme de décodage des codes linéaires qui peut être utilisé pour retrouver la clef lors d'une cryptanalyse linéaire. Notons que deux attaques sont proposées sur des schémas de chiffrement reconnus. Une cryptanalyse linéaire multiple sur la totalité du DES et une cryptanalyse différentielle multiple sur 18 tours du chiffrement PRESENT. Ces deux attaques sont, à ce jour, les meilleures attaques connues de leur catégorie sur ces chiffrements. Enfin, un appendice contient tous les détails techniques et preuves calculatoires permettant d'obtenir les résultats importants de ce document.

Cette thèse est subdivisée en deux parties. Dans la premier, je étudie la normalité projective de variétés symétriques, tandis que dans la deuxième je prouve des résultats partiels sur la classification de variétés symétriques de Fano (i.e. avec fibré anti-canonique ample). Dans [R. Chirivì, A. Maffei, Projective normality of complete symmetric varieties, Duke Math. J. 122 (1) (2004) 93-123], les authors ont prouvé la surjectivité du produit de sections de deux fibrés en droites globalement engendrés sur le plongement magnifique d'un espace symétrique (adjoint). Donné deux fibrés en droites amples sur une variété symétrique toroïdale compacte et lisse, je prouve deux critères pour la surjectivité du produit de sections. Grace à tels critères on se peut réduire à étudier le même problème sur la variété torique compacte (respectivement ouverte) associé. De plus, j'ai trouvé des familles de variétés symétriques toroïdales complètes, en particulier lesquelles avec rang 2, telles que le produit de sections de n'import quel fibré en droites ample est surjectif. Dans la deuxième part de ma thèse, j'ai d'abord classifié les variétés symétriques de Fano avec rang arbitraire et que l'on peut obtenir à partir du plongement magnifique par une succession des éclatements le long d'orbites fermées. Quand le rang est au plus trois, j'ai obtenu des résultats plus précis. Les variétés symétriques projectives avec rang un sont tous lisse et magnifique par un résultat classique dû à Akhiezer. J'ai classifié les variétés symétriques toroïdales projectives lisses de rang 2 dont le fibré anti-canonique est ample, respectivement globalement engendré. De plus, j'ai classifié les variétés symétriques de Fano avec rang 3 que l'on peut obtenir à partir du plongement magnifique par une succession des éclatements des sous-variétés G-stables. On peut observer que n'import quelle variété symétrique complete est dominé par une variété que l'on peut obtenir à partir du plongement magnifique par une succession des éclatements des sous-variétés G-stables de codimension 2.

.