Les réseaux Euclidiens sont un riche objet algébrique qui apparaît dans des contextes variés en mathématiques et en informatique. Cette thèse considère plusieurs aspects algorithmiques des réseaux. Le concept de réduction d'une base d'un réseau est étudié minutieusement : nous couvrons en particulier le spectre complet des compromis qualité-temps des algorithmes de réduction. D'une part, nous présentons et analysons des algorithmes rapides pour trouver une base assez courte (base LLL-réduite) d'un réseau donné arbitraire. D'autre part, nous proposons de nouvelles analyses pour des algorithmes (plus lents) permettant de calculer des bases très courtes (bases HKZ et BKZ-réduites). Cette étude des algorithmes de résolution efficace de problèmes portant sur les réseaux est complétée par une application constructive exploitant leur difficulté apparente. Nous proposons et analysons des schémas cryptographiques, dont la fonction de chiffrement NTRU, et les prouvons au moins aussi difficiles à casser que de résoudre des problèmes pires-cas bien spécifiés portant sur les réseaux.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00645387 |
| Date | 14 October 2011 |
| Creators | Stehlé, Damien |
| Publisher | Ecole normale supérieure de lyon - ENS LYON |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | habilitation ࠤiriger des recherches |
Page generated in 0.0022 seconds