Analyse probabiliste de la réduction des réseaux euclidiens cryptographiques

The topics covered in this thesis are the interfaces of cryptography, algorithms and analysis of algorithms. They focus on a particular area, the geometry of numbers, and in particular the reduction beyond Euclidean networks.Given the difficulty of an exact analysis of the LLL algorithm, we proposed a class of simplified models for the execution of the algorithm, the more simple, and already proposed by Madrisch Valley, to more complicated, which corresponds to LLL algorithm itself. We returned on the analysis of the simplest model by adopting the point of view of the chip firing game. We also tried to model in this part of cfg, main entrances that interested us, corresponding cryptographic systems. We were taken to three families of cryptographic networks: said Ajtai networks that give rise to piles "all very full," networks bag-to-back or NTRU networks, which give rise to piles of sand "with a single job "and finally networks Coppersmith, which give rise to piles of sand" with holes ". We then studied under a simplified execution model, but definitely closer to reality. We conducted a detailed analysis of this execution model: total analysis for the case of dimension 2, which corresponds to the 3-dimensional networks in the world, where the analysis of real LLL algorithm is already misunderstood --analyse partial general dimension. Finally, we made experiments to find an experimental validation of the assumptions that lead to simplified models.Les thèmes abordés dans cette thèse se situent aux interfaces de la cryptographie, de l'algorithmique et de l'analyse des algorithmes. Ils se concentrent sur un domaine particulier, celui de la géométrie des nombres et plus particulièrement , celui dela réduction des réseaux euclidiens.Devant la difficulté d'une analyse exacte de l'algorithme LLL, nous avons proposé toute une classe de modèles simplifiés pour l'exécution de l'algorithme, du plus simple, déjà proposé par Madrisch et Vallée, au plus compliqué, qui correspond à l'algorithme LLL lui-même. Nous sommes revenus sur l'analyse du modèle le plus simple en adoptant le point de vue du chip firing game. Nous avons aussi cherché à modéliser, dans ce cadre de cfg, les principales entrées qui nous intéressaient, correspondant à des réseaux cryptographiques. Nous avons été conduits à trois familles des réseaux cryptographiques : les réseaux dit réseaux d'Ajtai qui donnent lieu à des tas "tous très pleins", les réseaux sac-à-dos ou réseaux NTRU, qui donnent lieu à des tas de sable "avec un seul tas" et enfin les réseaux de Coppersmith, qui donnent lieu à des tas de sable "avec des trous". Nous avons ensuite étudié un modèle moins simplifié d'exécution, mais sans aucun doute plus proche de la réalité. Nous avons effectué une analyse précise de ce modèle d'exécution: analyse totale pour le cas de la dimension 2, qui correspond à la dimension 3 dans le monde des réseaux, où l'analyse du véritable algorithme LLL est déjà mal comprise --analyse partielle en dimension générale. Enfin, nous avons fait des expérimentations afin de rechercher une validation expérimentale des hypothèses qui mènent aux modèles simplifiés