Expander graphs and applications to information theoretic cryptography

Graphes expanseurs et applications à la cryptographie en théorie de l'information Cette thèse de doctorat porte sur la théorie spectrale des graphes et ses applications à la cryptographie dans le cadre de la théorie algorithmique de l'information. Nous commençons par présenter une introduction générale à la théorie spectrale des graphes. Nous expliquons d'abord les diverses relations entre le spectre des graphes réguliers et leurs propriétés combinatoires, en particulier leurs propriétés d'expansion. Nous poursuivons en présentant la plupart des outils techniques classiques dans ce domaine et nécessaires à notre contribution. Dans un deuxième temps, nous étudions plusieurs modèles de graphes aléatoires qui sont potentiellement utiles pour des applications pratiques. Les graphes étudiés ici ont relativement peu d'arêtes. Notre travail se concentre d'abord sur des expériences numériques sur ces graphes. Nous fournissons des preuves expérimentales que certains modèles de graphes aléatoires, tels que les graphes de Schreier aléatoires du groupe général linéaire ou les graphes issus des matrices de Toeplitz, sont de très bons expanseurs spectraux, du moins avec les paramètres que nous avons testés. De plus, nous fournissons des bornes théoriques sur l'espérance de la deuxième plus grande valeur propre de nos graphes de Schreier, ce qui offre des garanties sur l'expansion spectrale de tels objets mathématiques pour des paramètres fixés. Nous poursuivons notre étude avec quelques applications des propriétés spectrales et combinatoires des graphes aux problèmes de communication dans le cadre de la théorie algorithmique de l'information. Nous commençons par donner le contexte général de la complexité de Kolmogorov et de l'extractibilité de l'information mutuelle. Après ce travail introductif, nous détaillons nos outils techniques issus de la théorie des graphes qui sont ensuite utilisés pour prouver des propriétés d'inextractibilité de l'information mutuelle de certaines structures algébriques représentées sous forme de graphes (les graphes qui nous seront utiles ici seront beacuoup plus denses que précédement). Après avoir expliqué les bases nécessaires issues de la cryptographie en théorie de l'information, nous utilisons ces propriétés pour établir des bornes supérieures en pire cas sur la complexité de communication lors d'un accord de clé secrète avec trois participants, ainsi que d'autres résultats d'impossibilité sur des problèmes de communication en cryptographie.