Auswahl der wissenschaftlichen Literatur zum Thema „Algorithmes symétriques“

International audience We establish several properties of an algorithm defined by Mason and Remmel (2010) which inserts a positive integer into a row-strict composition tableau. These properties lead to a Littlewood-Richardson type rule for expanding the product of a row-strict quasisymmetric Schur function and a symmetric Schur function in terms of row-strict quasisymmetric Schur functions. Nous établissons plusieurs propriétés d'un algorithme défini par Mason et Remmel (2010), qui insère un entier positif dans un tableau dont la forme est une composition, avec ordre strict sur les lignes (row-strict). Ces propriétés conduisent à une règle de type Littlewood-Richardson pour étendre le produit d'une fonction de Schur quasi-symétrique "row-strict'' et d'une fonction de Schur symétrique en termes de fonctions de Schur quasi-symétriques "row-strict''.

International audience This paper aims at the development of innovating methods for optimum design for multidisciplinary optimization problems in the aeronautical context. The subject is the treatment of a problem of concurrent optimization in which the aerodynamicist interacts with the structural designer, in a parallel way in a symmetric Nash game. Algorithms for the calculation of the equilibrium point have been proposed and successfully tested for this coupled aero-structural shape optimization in a situation where the aerodynamical criterion is preponderant. Cet article a pour objectif le développement de méthodes numériques innovantes pour la conception optimale de forme pour les problèmes d’optimisation multidisciplinaire dans un contexte aéronautique. On cherche à traiter un problème d’optimisation concourante où le concepteur aérodynamique interagit avec le concepteur structural, parallèlement dans un jeu symétrique de Nash. On a proposé et expérimenté avec succès des algorithmes de calcul d’équilibre pour cette optimisation couplée aéro-structurale dans une situation où le critère aérodynamique est prépondérant.

International audience Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group $S_n$. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We show that the problem $\mathrm{KRONCOEFF}$ of computing Kronecker coefficients is very difficult. More specifically, we prove that $\mathrm{KRONCOEFF}$ is #$\mathrm{P}$-hard and contained in the complexity class $\mathrm{GapP}$. Formally, this means that the existence of a polynomial time algorithm for $\mathrm{KRONCOEFF}$ is equivalent to the existence of a polynomial time algorithm for evaluating permanents. Les coefficients de Kronecker sont les multiplicités dans la décomposition du produit tensoriel de deux représentations irréductibles du groupe symétrique. On peut aussi les voir comme les coefficients du développement du produit interne des polynômes de Schur. Nous montrons que le problème $\mathrm{KRONCOEFF}$ de calculer les coefficients de Kronecker est très difficile. Plus précisément, nous prouvons que $\mathrm{KRONCOEFF}$ est #$\mathrm{P}$-dur et que $\mathrm{KRONCOEFF}$ est dans la classe de complexité $\mathrm{GapP}$. Cela veut dire qu'il existe un algorithme pour $\mathrm{KRONCOEFF}$ s'exécutant en temps polynomial si et seulement s'il existe un algorithme pour l'évaluation du permanent s'exécutant en temps polynomial.

International audience We give a new construction of a Hopf subalgebra of the Hopf algebra of Free quasi-symmetric functions whose bases are indexed by objects belonging to the Baxter combinatorial family (\emphi.e. Baxter permutations, pairs of twin binary trees, \emphetc.). This construction relies on the definition of the Baxter monoid, analog of the plactic monoid and the sylvester monoid, and on a Robinson-Schensted-like insertion algorithm. The algebraic properties of this Hopf algebra are studied. This Hopf algebra appeared for the first time in the work of Reading [Lattice congruences, fans and Hopf algebras, \textitJournal of Combinatorial Theory Series A, 110:237–273, 2005]. Nous proposons une nouvelle construction d'une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les objets de la famille combinatoire de Baxter (\emphi.e. permutations de Baxter, couples d'arbres binaires jumeaux, \emphetc.). Cette construction repose sur la définition du mono\"ıde de Baxter, analogue du mono\"ıde plaxique et du mono\"ıde sylvestre, et d'un algorithme d'insertion analogue à l'algorithme de Robinson-Schensted. Les propriétés algébriques de cette algèbre de Hopf sont étudiées. Cette algèbre de Hopf est apparue pour la première fois dans le travail de Reading [Lattice congruences, fans and Hopf algebras, \textitJournal of Combinatorial Theory Series A, 110:237–273, 2005].

International audience In a recent paper, Diaconis, Ram and I constructed Markov chains using the coproduct-then-product map of a combinatorial Hopf algebra. We presented an algorithm for diagonalising a large class of these "Hopf-power chains", including the Gilbert-Shannon-Reeds model of riffle-shuffling of a deck of cards and a rock-breaking model. A very restrictive condition from that paper is removed in my thesis, and this extended abstract focuses on one application of the improved theory. Here, I use a new technique of lumping Hopf-power chains to show that the Hopf-power chain on the algebra of quasisymmetric functions is the induced chain on descent sets under riffle-shuffling. Moreover, I relate its right and left eigenfunctions to Garsia-Reutenauer idempotents and ribbon characters respectively, from which I recover an analogous result of Diaconis and Fulman (2012) concerning the number of descents under riffle-shuffling. Dans un récent article avec Diaconis et Ram, nous avons construit des chaînes de Markov en utilisant une composition du coproduit et produit d’une algèbre de Hopf combinatoire. Nous avons présenté un algorithme pour diagonaliser une large classe de ces “chaînes de Hopf puissance”, en particulier nous avons diagonalisé le modèle de Gilbert-Shannon-Reeds de mélange de cartes en “riffle shuffle” (couper en deux, puis intercaler) et un modèle de cassage de pierres. Dans mon travail de thèse, nous supprimons une condition très restrictive de cet article, et ce papier se concentre surune application de cette amélioration. Nous utilisons ici une nouvelle technique de projection de chaînes de Hopf puissance pour montrer que la chaîne de Hopf puissance sur l’algèbre des fonctions quasi-symétriques est la chaîne de Markov induite sur les ensembles des descentes dans le “riffle shuffling”. De plus, nous faisons le lien entre les fonctions propres à droite et à gauche et respectivement les idempotents de Garsia-Reutenauer et les caractères en rubans, ce qui nous permet de retrouver un résultat analogue à Diaconis et Fulman (2012) concernant le nombre de descentes dans le “riffle shuffling”.

L’objectif de cette thèse est de proposer de nouvelles pistes de recherche dans l’état de l’art afin de sécuriser les algorithmes cryptographiques au sein d’un circuit électronique. Notre axe d’étude principal s’articule autour de la contre-mesure des implémentations à seuil, résistante contre les attaques par observations en présence de glitches. Ces derniers phénomènes apparaissent dans un circuit électronique de manière aléatoire et sont à l’origine de nombreuses attaques en cryptanalyse. Nous étudions l’application des implémentations à seuil sur la cryptographie symétrique. Dans un premier temps, nous contribuons à la littérature cryptographique par la conception de nouvelles implémentations à seuil applicables sur un grand nombre d’algorithmes symétriques. Les travaux réalisés sont appuyés par des preuves mathématiques formelles et permettent de contrer les attaques physiques par observations en présence de glitches. Par ailleurs, nos recherches ont également débouché à la proposition de deux brevets au sein de l’entreprise STMicroelectronics, participant ainsi au processus d’innovation industriel. Dans un second temps, nous nous intéressons à l’étude de l’algorithme symétrique SM4 et sa résistance face à la cryptanalyse actuelle. Les travaux obtenus permettent de centraliser les différentes implémentations du SM4 sécurisées contre les attaques par observations proposées dans l’état de l’art et d’offrir une visibilité sur les performances de ces constructions. Nous contribuons également à la recherche académique par la première proposition d’une implémentation à seuil du SM4, mathématiquement résistante contre les attaques par observations en présence de glitches
The goal of this thesis is to contribute to the state-of-the-art by proposing new areas of research in order to secure cryptographic algorithms within an embedded device.Our main focal axis is organized around the countermeasure called threshold implementations which is known to be resistant against side-channel analysis attacks in the presence of glitches.These latter phenomenon occur randomly within an electronic circuit and lead to numerous attacks in cryptanalysis. We study the application of threshold implementations on symmetric-key cryptography.In a first phase, we participate to the cryptographic litterature by designing new threshold implementations easily applicable on a large variety of symmetric-key algorithms. Our countermeasures are provable mathematically secured against side-channel analysis attacks in the presence of glitches. In comparison with the recent publications of the state-of-the-art, we adress new issues and we assure similar or better performances. Therefore, our research has resulted in two patents within STMicroelectronics, thereby contributing to the industrial innovation process.In a second phase, we are interested in the study of the symmetric-key algorithm SM4 and its resistance against side-channel analysis attacks. The works obtained allow to centralize the proposed SM4 countermeasures against side-channel analysis attacks of the state-of-the-art and offer a visibility on the software performances of these constructions. We finally introduce the first threshold implementation of the SM4 algorithm. Our construction is provably mathematically resistant against side-channel analysis attacks in the presence of glitches

Cette these se divise en deux parties independantes. La premiere partie concerne la resolution de systemes lineaires de grande taille sur des systemes a memoire distribuee. L'algorithme utilise la factorisation lu et la resolution des deux systemes triangulaires. Nous donnons une description detaillee de cet algorithme, et discutons les choix qui ont ete realises lors de son implantation. Nous montrons aussi que cet algorithme est numeriquement stable, et permet de preserver le caractere creux de la matrice. Au cours de son execution, les taches sont equitablement reparties entre les differents processeurs. Pour montrer les performances de l'algorithme, nous resolvons plusieurs problemes issus de la physique sur diverses machines cibles a memoire distribuee. Nous illustrons l'influence de certains parametres de l'algorithme sur la qualite de la solution et sur la vitesse de convergence. Dans la seconde partie, nous nous interessons a une categorie d'algorithmes de reordonnancement pour des matrices non symetriques. Le but initial du reordonnancement est d'amener les pivots de plus large module sur la diagonale de la matrice, pour ameliorer la qualite numerique des solutions. Nous presentons en detail diverses variantes de ces algorithmes. Nous envisageons aussi la possibilite d'utiliser en plus du reordonnancement, des techniques de scaling. Enfin nous presentons des experimentations numeriques qui permettent de comparer les algorithmes de reordonnancement. Nous montrerons l'impact de ces techniques lorsqu'elles sont utilisees un amont d'algorithmes directs ou iteratifs de resolution de systemes lineaires.

Les travaux de cette thèse portent sur les critères de sécurité des
algorithmes de chiffrement à clé secrète et ont été menés suivant deux
axes. Le premier concerne la sécurité des chiffrements symétriques
itératifs par blocs contre les attaques par distingueur sur le dernier
tour. Les résultats portent en particulier sur la généralisation d'une
attaque différentielle d'ordre supérieur menée sur l'algorithme
MISTY1. L'origine de cette attaque ainsi que de sa généralisation a pu
être expliquée grâce aux propriétés du spectre de Walsh des fonctions
de non-linéarité maximale utilisées. Ainsi il a été possible
d'élaborer une attaque générique sur tous les chiffrements de Feistel
à cinq tours utilisant des fonctions dont le spectre de Walsh est
divisible par une grande puissance de 2 car cette propriété permet
d'obtenir une borne supérieure sur le degré de la composition de
telles fonctions, nettement plus faible que la borne
triviale. Cette attaque suggère ainsi un nouveau critère de sécurité
qui porte sur la divisibilité du spectre de Walsh des fonctions de
tour utilisées dans les chiffrements itératifs par blocs. La deuxième
partie de la thèse porte sur l'étude des fonctions booléennes
symétriques, et en particulier sur l'existence éventuelle de
propriétés cryptographiques. À partir d'une propriété structurelle de
périodicité d'une représentation d'une fonction booléenne symétrique,
les propriétés de degré algébrique, d'équilibre, de résilience, de
critère de propagation et de non-linéarité ont été étudiées, ce qui a
permis d'améliorer les résultats existants. Par ailleurs, le calcul
explicite du spectre de Walsh des fonctions booléennes symétriques de
degré 2 et 3 a été réalisé, ainsi que la détermination de toutes les
fonctions symétriques équilibrées de degré inférieur ou égal à 7,
indépendamment du nombre de variables.

Dans de nombreux domaines scientifiques il est necessaire de compter des objets ou de realiser de longs calculs pour valider des modeles ou tester des conjectures. L'informatique theorique produit a cette fin de nombreux algorithmes et methodes ayant pour vocation d'aider a resoudre ces problemes. Il n'est pas surprenant que la combinatoire algebrique joue ici un grand role en offrant des moyens de compter des objets ou d'etablir des relations sur ces objets. Aussi, les liens entre combinatoire algebrique, fonctions symetriques et theorie des groupes conduisent a examiner l'application de ses methodes en physique theorique ou il est necessaire de produire des calculs de grande envergure sur les representations des groupes non compacts. La grande complexite de ces algorithmes requiert le developpement de nouvelles methodes pour calculer plus facilement la decomposition de certaines classes de produit tensoriels et plethysmes. Ceci permet alors la construction de nouveaux algorithmes plus efficaces utilises pour des calculs sur les modeles physiques. Cette these presente apres des rappels theoriques des techniques utilisees pour les calculs sur les representations de dimension infinie de certains groupes non compacts, parmi lesquels le groupe symplectique reel. Pour ce groupe nous donnons deux exemples d'illustration. Plus generalement sont presentes des exemples de calcul realises avec schur, programme augmente des resultats presentes. Pour certains cas on donne des exemples de programme maple montrant la simplicite des nouvelles methodes de calculs. De nouveaux resultats sont aussi presentes pour les representations irreductibles des groupes non compacts so*(2n), sp(2n, r) et u(p,q) et pour les sous-groupes finis du groupe exceptionnel g 2

Les travaux de la thèse se focalisent sur la protection des réseaux de distribution HTA en présence des générateurs distribués (éoliennes, fermes solaires,...). Dans un premier temps, un état de l’art a été réalisé sur les comportements des générateurs en creux de tension, leurs impacts sur le système de protection et les pistes de solution proposées pour y remédier. L’étape suivante est la mise au point d’algorithmes directionnels de détection de défauts, sans mesure de tension. Ces algorithmes s’appuient sur la décomposition en composantes symétriques des courants mesurés. Ces relais doivent empêcher le déclenchement intempestif de protections de surintensité dû au courant de défaut provenant des générateurs distribués. Ils sont moins coûteux par rapport à ceux traditionnels car les capteurs de tension, qui sont indispensables pour ces derniers, peuvent être enlevés. Après détection d’un défaut sur critère de seuil simple (max de I ou max de I résiduel), la direction est évaluée à l’aide d’un algorithme en delta basé sur les rapports courants inverse-homopolaire ou inverse-direct, selon le type de défaut (monophasé ou biphasé). En se basant sur ces rapports, un classifieur SVM (Support Vector Machines), entrainé préalablement à partir des simulations, donne ensuite l’estimation de la direction du défaut (amont ou aval par rapport au relais). La bonne performance de ces algorithmes a été montrée dans la thèse pour différents paramètres du réseau et en présence de différents types de générateurs. Le développement de tels algorithmes favorise la mise en œuvre des protections en réseau, qui pourraient être installées dans les futurs Smart Grids
This research focuses on the protection of MV distribution networks with Distributed Generators (DGs), such as wind farms or photovoltaic farms, etc. First, the state of art is carried out on fault behaviour of DGs, their impacts on protection system and the mitigation solutions. Next, algorithms are developed for directional relays without voltage sensors. Based on the symmetrical component method, these algorithms help the overcurrent protections to avoid the false tripping issue due to fault contribution of DGs. With the suppression of voltage sensors, such directional relays become cheaper in comparison with the traditional ones. Following the fault detection (the phase or residual current reaches the pick-up value) and depending on fault type (line-to-ground or line-to-line fault), the ratios between the variation (before and during fault) of negative-zero sequence or negative-positive sequence currents are calculated. From these ratios, a SVM (Support Vector Machines) classifier estimates the fault direction (upstream or downstream the detector). The classifier is trained beforehand from transient simulations. This survey shows good performances of the directional algorithms with different network parameters and different kinds of DGs. Such algorithms could be implemented in protections along the feeders in the future smart grids

Les réseaux de distribution moyenne tension sont victimes de défauts qui doivent être détectés et éliminés le plus rapidement possible, puis localisés plus précisément afin de permettre l'intervention d'équipes de réparation. Ce travail de recherche porte sur l'utilisation des composantes symétriques (homopolaires, directes et inverses) et harmoniques par des algorithmes de protection et de localisation de défauts. Une première partie théorique a permis de mettre en évidence les propriétés de la décomposition symétrique et harmonique des signaux tension et courant, et de calculer les composantes des courants issus des différents défauts considérés. Les algorithmes de protection directionnels développés par la suite ont comme principal avantage de pouvoir se passer de capteurs de tension dans la plupart des configurations. L'information harmonique, lorsqu'elle est disponible, amène à une amélioration des performances de ces algorithmes, sans pour autant être réellement indispensable. Les algorithmes de localisation mis au point ne requièrent pour fonctionner que la connaissance topologique du réseau et non pas celle des caractéristiques électriques de chaque tronçon. Ils aboutissent eux aussi à une diminution du nombre de capteurs nécessaires. Leur généralisation nous conduit à un système global de localisation applicable quels que soient le nombre et l'emplacement des capteurs. Tous ces algorithmes ont été testés et validés par simulation sur un grand nombre de configurations et de cas. Nous avons ainsi clairement identifié leurs limites et leurs performances. Deux régimes de neutre ont été pris en compte: neutre résistif et neutre compensé, ainsi que deux types de défaut: monophasé et biphasé
The medium voltage distribution networks are victims of faults which must be detected and eliminated as soon as possible, then more precisely localised in order to allow repairing staff to operate. This research work relates to the use of the symmetrical (homopolar, positive and onegative sequence) and harmonic components by protection and localization algorithms. A first theoretical part made it possible to highlight the properties of the symmetrical and harmonic decomposition of the voltage and current signals, and to calculate the components of the currents resulting from the various faults considered. The directional protection algorithms developed thereafter have as principal advantage of being able to work without voltage sensors in most configurations. Harmonic information, when it is available, leads to an improvement of the performances of these algorithms, without being really essential. The algorithms of localization developed require to function only the topological knowledge of the network and not that of the electric characteristics of each section. They also lead to a reduction in the number of sensors necessary. Their generalization leads us to a total system of applicable localization whatever the number and situation of the sensors. All these algorithms were tested and validated by simulation on a great number of configurations and cases. We thus clearly identified their limits and their performances. Two kind of neutral grounding were taken into account: resistive neutral and compensated neutral, like two types of fault : single-phase current and two-phase

L'objet de cette thèse concerne les propriétés du groupe symétrique à travers deux problèmes. Le premier consiste à étudier l'action du groupe symétrique sur la fraction (...). En appliquant certaines opérations sur les graphes et les cartes, nous donnons des algorithmes et des formules combinatoires pour déterminer complètement la fraction réduite suivante : (...). L'auteur C. Greene a introduit cette fraction rationnelle pour généraliser des identités liées a la règle de Murnaghan-Nakayama. Nous utilisons (...) pour établir un nouvel algorithme de décomposition en éléments simples à l'aide des graphes. Dans la seconde partie, nous cherchons a développer les puissances paires du Vandermonde au moyen de fonctions symétriques. En particulier, nous proposons une écriture hyperdéterminantale des coefficients du développement des puissances paires du Vandermonde dans la base des fonctions de Schur. Nous obtenons plusieurs identités reliant les puissances paires du Vandermonde et les polynômes de Jack. Puis nous introduisons une q-déformation des puissances paires du Vandermonde que nous exprimons grâce aux polynômes de Macdonald

La sécurité des transmissions et du stockage des données est devenue un enjeu majeur de ces dernières années et la cryptologie, qui traite de la protection algorithmique de l'information, est un sujet de recherche extrêmement actif. Elle englobe la conception d'algorithmes cryptographiques, appelée cryptographie, et l'analyse de leur sécurité, appelée cryptanalyse.Dans cette thèse, nous nous concentrons uniquement sur la cryptanalyse, et en particulier celle des algorithmes de chiffrement symétrique, qui reposent sur le partage d'un même secret entre l'entité qui chiffre l'information et celle qui la déchiffre. Dans ce manuscrit, trois attaques contre des algorithmes de chiffrement symétriques sont présentées. Les deux premières portent sur deux candidats de l'actuelle compétition cryptographique CAESAR, les algorithmes AEZ et NORX, tandis que la dernière porte sur l'algorithme Kravatte, une instance de la construction Farfalle qui utilise la permutation de la fonction de hachage décrite dans le standard SHA-3. Les trois algorithmes étudiés présentent une stratégie de conception similaire, qui consiste à intégrer dans une construction nouvelle une primitive, i.e. une fonction cryptographique élémentaire, déjà existante ou directement inspirée de travaux précédents.La compétition CAESAR, qui a débuté en 2015, a pour but de définir un portefeuille d'algorithmes recommandés pour le chiffrement authentifié. Les deux candidats étudiés, AEZ et NORX, sont deux algorithmes qui ont atteint le troisième tour de cette compétition. Les deux attaques présentées ici ont contribué à l'effort de cryptanalyse nécessaire dans une telle compétition. Cet effort n'a, en l'occurrence, pas permis d'établir une confiance suffisante pour justifier la présence des algorithmes AEZ et NORX parmi les finalistes.AEZ est une construction reposant sur la primitive AES, dont l'un des principaux objectifs est d'offrir une résistance optimale à des scénarios d'attaque plus permissifs que ceux généralement considérés pour les algorithmes de chiffrement authentifié. Nous montrons ici que dans de tels scénarios il est possible, avec une probabilité anormalement élevée, de retrouver l'ensemble des secrets utilisés dans l'algorithme.NORX est un algorithme de chiffrement authentifié qui repose sur une variante de la construction dite en éponge employée par exemple dans la fonction de hachage Keccak. Sa permutation interne est inspirée de celles utilisées dans BLAKE et ChaCha. Nous montrons qu'il est possible d'exploiter une propriété structurelle de cette permutation afin de récupérer la clé secrète utilisée. Pour cela, nous tirons parti du choix des concepteurs de réduire les marges de sécurité dans le dimensionnement de la construction en éponge.Enfin, la dernière cryptanalyse remet en cause la robustesse de l'algorithme Kravatte, une fonction pseudo-aléatoire qui autorise des entrées et sorties de taille variable. Dérivée de la permutation Keccak-p de SHA-3 au moyen de la construction Farfalle, Kravatte est efficace et parallélisable. Ici, nous exploitons le faible degré algébrique de la permutation interne pour mettre au jour trois attaques par recouvrement de clé : une attaque différentielle d'ordre supérieur, une attaque algébrique "par le milieu" et une attaque inspirée de la cryptanalyse de certains algorithmes de chiffrement à flot
Nowadays, cryptology is heavily used to protect stored and transmitted data against malicious attacks, by means of security algorithms. Cryptology comprises cryptography, the design of these algorithms, and cryptanalysis, the analysis of their security.In this thesis, we focus on the cryptanalysis of symmetric encryption algorithms, that is cryptographic algorithms that rely on a secret value shared beforehand between two parties to ensure both encryption and decryption. We present three attacks against symmetric encryption algorithms. The first two cryptanalyses target two high profile candidates of the CAESAR cryptographic competition, the AEZ and NORX algorithms, while the last one targets the Kravatte algorithm, an instance of the Farfalle construction based on the Keccak permutation. Farfalle is multipurpose a pseudo-random function (PRF) developed by the same designers' team as the permutation Keccak used in the SHA-3 hash function.The CAESAR competition, that began in 2015, aims at selecting a portfolio of algorithms recommended for authenticated encryption. The two candidates analysed, AEZ and NORX, reached the third round of the CAESAR competition but were not selected to be part of the finalists. These two results contributed to the cryptanalysis effort required in such a competition. This effort did not establish enough confidence to justify that AEZ and NORX accede to the final round of the competition.AEZ is a construction based on the AES primitive, that aims at offering an optimal resistance against more permissive attack scenarios than those usually considered for authenticated encryption algorithms. We show here that one can recover all the secret material used in AEZ with an abnormal success probability.NORX is an authenticated encryption algorithm based on a variant of the so-called sponge construction used for instance in the SHA-3 hash function. The internal permutation is inspired from the one of BLAKE and ChaCha. We show that one can leverage a strong structural property of this permutation to recover the secret key, thanks to the designers' non-conservative choice of reducing the security margin in the sponge construction.Finally, the last cryptanalysis reconsiders the robustness of the Kravatte algorithm. Kravatte is an efficient and parallelizable PRF with input and output of variable length. In this analysis, we exploit the low algebraic degree of the permutation Keccak used in Kravatte to mount three key-recovery attacks targeting different parts of the construction: a higher order differential attack, an algebraic meet-in-the-middle attack and an attack based on a linear recurrence distinguisher

Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur la construction de plusieurs structures combinatoires et algébriques sur différentes espèces d'arbres. Après avoir défini un analogue du monoïde plaxique dont les classes d'équivalence sont indexées par les couples d'arbres binaires jumeaux, nous proposons un analogue de la correspondance de Robinson-Schensted dans ce contexte. À partir de ce monoïde, nous construisons une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les couples d'arbres binaires jumeaux. Ensuite, nous proposons un foncteur combinatoire de la catégorie des monoïdes vers la catégorie des opérades ensemblistes. En utilisant ce foncteur, nous construisons plusieurs opérades qui mettent en jeu divers objets combinatoires. Par le biais d'une construction qui à une opérade associe une algèbre de Hopf non commutative, nous obtenons à partir de l'une des opérades obtenue par notre construction, une algèbre de Hopf basée sur les forêts ordonnées d'arbres plans enracinés. Nous proposons une réalisation polynomiale de cette dernière. Finalement, nous établissons certaines propriétés vérifiées par les arbres binaires équilibrés dans le treillis de Tamari. Nous montrons que l'ensemble des arbres binaires équilibrés y est clos par intervalle et que les intervalles d'arbres binaires équilibrés ont la forme d'hypercubes. Dans l'objectif de dénombrer ces intervalles, nous introduisons une nouvelle sorte de grammaires d'arbres, les grammaires synchrones. Celles-ci permettent d'obtenir une équation fonctionnelle de point fixe pour la série génératrice des arbres qu'elles engendrent

Nous étudions les propriétés cryptographiques des fonctions booléennes telles que la résilience, le critère de propagation (PC) et le degré algébrique. Nous introduisons également un algorithme permettant d'augmenter la robustesse des systèmes de chiffrement symétrique en renforçant la confusion de ces systèmes. Nous présentons tout d'abord un état de l'art des bornes inférieures et supérieures sur le nombre de fonctions booléennes m-résilientes à n variables, que nous enrichissons de quelques compléments. Nous proposons ensuite une nouvelle borne supérieure sur le nombre de ces fonctions qui améliore significativement les bornes supérieures connues pour des ordres m compris entre n/2 et 3n/4. Puis, nous nous intéressons à la construction de fonctions booléennes équilibrées satisfaisant PC(l) et nous recherchons le plus haut degré algébrique atteint par ces fonctions. Nous étudions les fonctions de Maiorana-MacFarland dans ce contexte et construisons des fonctions booléennes équilibrées ayant un degré algébrique élevé et satisfaisant PC(l) pour des valeurs de l pour lesquelles de telles fonctions n'étaient pas connues auparavant. Nous étudions ensuite les fonctions booléennes symétriques. Nous montrons que celles qui vérifient PC(l) pour tout l fixé avec l>=2 sont les fonctions symétriques quadratiques. Ce résultat dont la preuve est très simple, implique en particulier comme corollaire immédiat un résultat connu : les seules fonctions symétriques courbes sont les fonctions symétriques quadratiques. Enfin, nous proposons une nouvelle brique de confusion pour le chiffrement symétrique.