Dissertation/ Thesis
Euclidean lattices: algorithms and cryptography ; Réseaux Euclidiens : Algorithmes et Cryptographie
| العنوان: | Euclidean lattices: algorithms and cryptography ; Réseaux Euclidiens : Algorithmes et Cryptographie |
|---|---|
| المؤلفون: | Stehlé, Damien |
| المساهمون: | Computer arithmetic (ARENAIRE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Ecole normale supérieure de lyon - ENS LYON, Karim BELABAS |
| المصدر: | https://theses.hal.science/tel-00645387 ; Cryptography and Security [cs.CR]. Ecole normale supérieure de lyon - ENS LYON, 2011. |
| بيانات النشر: | HAL CCSD |
| سنة النشر: | 2011 |
| المجموعة: | HAL Lyon 1 (University Claude Bernard Lyon 1) |
| مصطلحات موضوعية: | Euclidean lattices, LLL/HKZ/BKZ reductions, lattice-based cryptography, computer algebra, hybrid symbolic-numeric algorithms, analysis of algorithms, Réseaux Euclidiens, réductions LLL/HKZ/BKZ, cryptographie reposant sur les réseaux Euclidiens, algorithmes hybrides numériques-algébriques, analyse d'algorithmes, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] |
| الوصف: | Euclidean lattices are a rich algebraic object that occurs in a wide variety of contexts in mathematics and in computer science. The present thesis considers several algorithmic aspects of lattices. The concept of lattice basis reduction is thoroughly investigated: in particular, we cover the full range of time-quality trade-offs of reduction algorithms. On the first hand, we describe and analyse fast algorithms for finding a relatively short basis (LLL-reduced basis) of an arbitrary given lattice. On the second hand, we propose novel analyses for (slower) algorithms that compute very short bases (HKZ-reduced and BKZ-reduced bases). This study on how to efficiently solve algorithmic problems on lattices is completed by a constructive application exploiting their apparent hardness. We propose and analyze cryptographic schemes, including the NTRU encryption function, and prove them at least as secure as well-specified worst-case problems on lattices. ; 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. |
| نوع الوثيقة: | doctoral or postdoctoral thesis |
| اللغة: | English |
| Relation: | tel-00645387; https://theses.hal.science/tel-00645387; https://theses.hal.science/tel-00645387/document; https://theses.hal.science/tel-00645387/file/HDR_full.pdf |
| الاتاحة: | https://theses.hal.science/tel-00645387 https://theses.hal.science/tel-00645387/document https://theses.hal.science/tel-00645387/file/HDR_full.pdf |
| Rights: | info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.1A82A7D5 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |