Multivariate Cryptography can be defined as public key cryptography based on the computational hardness of solving a system of polynomial equations in several variables. Although research on such schemes appeared in the early 80s, it has really been developed over the last ten years, and has given rise to several promising proposals, such as the HFE cryptosystem and the SFLASH signature scheme. Multivariate schemes therefore stand as possible alternatives to the traditional schemes based on problems from number theory, and as efficient solutions for the implementation of public key functionality. At the Eurocrypt 2005 conference, Fouque, Granboulan and Stern proposed a new cryptanalytic approach for multivariate schemes based on the analysis of invariants related to the differential of the public key, and demonstrated the relevance of this approach by cryptanalyzing the PMI scheme proposed by Ding. In this thesis, we develop the differential approach proposed by Fouque et al. in two directions. The first one consists of a combinatorial treatment of the dimensional invariants of the differential, which enables us to show that an HFE public key can be distinguished from a random system of quadratic equations in quasipolynomial time, countering the classical security argument based on the generic intractability of solving such a system of equations. A second application of the same approach leads to a cryptanalysis of a variation of HFE proposed by Ding and Schmidt at PKC 2005. The second development of this thesis is the exposure of functional invariants of the differential, which enables us to completely cryptanalyze the SFLASH scheme.
