Algorithmic aspects of algebraic lattices - Thèses de Sorbonne Université Accéder directement au contenu
Thèse Année : 2020

Algorithmic aspects of algebraic lattices

Aspects algorithmiques des réseaux algébriques

Thomas Espitau

Résumé

Lattices are mathematical objects generalizing the concrete idea of grid embedded in the plane. They play a fundamental role in the study of various subfields of mathematics and computer science, in particular, algebraic number theory and cryptography. This thesis deals with so-called "algebraic" lattices, that is, constructed above a maximal order of a number field, with a particular emphasis on computational methods. After developing generic techniques enabling the certified manipulation of such objects, we will turn to the development of an effective algorithms for the reduction of lattices over cyclotomic fields, in particular exploiting their natural recursive and symplectic structure. This study is then used for the resolution of a central problem in algorithmic number theory, namely the principal ideal problem, consisting of the finding of a generator a principal ideal in a number field. We eventually look at the implications of these works in public-key cryptography, where we present attacks on a fully homomorphic encryption scheme and on the BLISS digital signature.
Les réseaux sont des objets mathématiques qui généralisent l'idée concrète de grille dans le plan. Ils jouent un rôle fondamental dans l’étude de nombreux domaines des mathématiques et de l'informatique, notamment la théorie algébrique des nombres et la cryptographie. Ce manuscrit a pour objet les réseaux dits “algébriques", c'est-à-dire construits au-dessus d'un ordre maximal de corps de nombres, en se concentrant particulièrement sur les méthodes calculatoires. Après avoir développé des méthodes génériques autorisant la manipulation certifiée de tels objets, nous nous intéresserons à l’élaboration d'une algorithmique plus efficace permettant la réduction sur des corps cyclotomiques, utilisant en particulier leur structure récursive et symplectique. Ces dernières avancées seront alors utilisées pour la résolution d'un problème central en théorie algorithmique des nombres : le problème de l'idéal principal, qui consiste en la détermination d'un générateur d'un idéal principal d'un corps de nombre. Nous étudierons enfin les implications de cette étude en cryptographie à clef-publique, où nous présenterons des attaques sur des schémas d'encryption totalement homomorphes et sur la signature digitale BLISS.
Fichier principal
Vignette du fichier
ESPITAU_Thomas_these_2020.pdf (2.96 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)

Dates et versions

tel-04043054 , version 1 (23-03-2023)

Identifiants

  • HAL Id : tel-04043054 , version 1

Citer

Thomas Espitau. Algorithmic aspects of algebraic lattices. Cryptography and Security [cs.CR]. Sorbonne Université, 2020. English. ⟨NNT : 2020SORUS474⟩. ⟨tel-04043054⟩
136 Consultations
95 Téléchargements

Partager

Gmail Facebook X LinkedIn More