Abstract
This PhD thesis is a work on spectral graph theory and its applications to cryptography in the framework of algorithmic theory of information. We start by presenting a general introduction on spectral graph theory. We first explain the various connections between the spectrum of regular graphs and their combinatorial properties, in particular their expansion properties. We follow by presenting most of the technical tools that are classical in the field and necessary for our contribution. Secondly, we study several models of random graphs that are potentially useful for practical applications. The graphs we study here are sparse. Our work first focus on numerical experiments on such graphs. We provide experimental evidence that some models of random graphs such as random Schreier graphs of the general linear group or graphs from Toeplitz matrices are very good spectral expander, at least for the set of parameters we tested. Moreover, we give some theoretical bounds on the expected second largest eigenvalue of Schreier graphs that gives guarantees on the spectral expansion of such mathematical objects for fixed parameters. We follow our study with some applications of spectral and combinatorial properties of graphs to communication problems in the framework of algorithmic information theory. We start by giving the general context on Kolmogorov complexity and mutual information extractability. After this introductory work, we detail our technical tools from graph theory that are then used to prove mutual information inextractability properties of some algebraic structures represented as graphs (the graphs that will be of use here are much denser than that of the previous chapter). After explaining the background needed from information theoretic cryptography, we use these properties to establish worst case upper bounds on communication complexity on secret key agreement with three participants, and other impossibility results on communication problems in cryptography.