Analyse probabiliste de la réduction des réseaux euclidiens cryptographiques
Institution:
CaenDisciplines:
Directors:
Abstract EN:
The topics addressed in this thesis belong to the interface between cryptography, algorithmics, and analysis of algorithms. They focus to a particular area, the geometry of numbers, in particular lattice reduction. Given the difficulty of an exact analysis of the LLL algorithm, we proposed a class of simplified models for the execution of the algorithm, ranging from the simplest one, already proposed by Madrisch and Vallée, to the most complex, which is the LLL algorithm itself. We first returned to the analysis of the simplest model and adopted there the perspective of the ``chip firing game''. From this perspective, we also described models for the different inputs of interest, corresponding to cryptographic systems. We were then led to three families of ``cryptographic lattices'': Ajtai's lattices give rise to sandpiles, whose piles are all ``full'' ; Knapsack or NTRU lattices give rise to sandpiles ``with only one pile''; finally Coppersmith's lattices give rise to sandpiles with ``holes''. Then we studied a model for the execution which was less simplified, but probably more realistic. We performed a detailed analysis of this model: a complete analysis in the two dimensional case, which corresponds to three-dimensional lattices, where the analysis of the exact LLL algorithm is not yet known, together with a partial analysis in general dimensions. Finally, we conducted experiments, in order to obtain an experimental validation of the assumptions that lead to simplified models.
Abstract FR:
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 delà 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.