Direction de recherche : Antoine JOUX

Co-encadrement : FOUQUE Pierre-Alain

Aspects algorithmique des réseaux algébriques

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 recursive 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 ideal 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.

Publications 2016-2020

• 2020
  • Th. Espitau : “Algorithmic aspects of algebraic lattices”, soutenance de thèse, soutenance 14/01/2020, direction de recherche Joux, Antoine, co-encadrement : Fouque, Pierre-Alain (2020)
  • Th. Espitau, A. Joux, N. Kharchenko : “On a Dual/Hybrid Approach to Small Secret LWE”, Progress in Cryptology – INDOCRYPT 2020, vol. 12578, Lecture Notes in Computer Science, Bangalore, India, pp. 440-462, (Springer), (ISBN: 978-3-030-65277-7) (2020)
  • Th. Espitau, A. Joux : “Certified lattice reduction”, Advances in Mathematics of Communications, vol. 14 (1), pp. 137-159, (AIMS) (2020)
• 2018
  • Th. Espitau, P.‑A. Fouque, B. Gérard, M. Tibouchi : “Loop-Abort Faults on Lattice-Based Signatures and Key Exchange Protocols”, IEEE Transactions on Computers, vol. 67 (11), pp. 1535-1549, (Institute of Electrical and Electronics Engineers) (2018)
  • J. Bootle, C. Delaplace, Th. Espitau, P.‑A. Fouque, M. Tibouchi : “LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS”, ASIACRYPT 2018 - 24^th International Conference on the Theory and Application of Cryptology and Information Security, vol. 11272, Lecture Notes in Computer Science, Brisbane, QLD, Australia, pp. 494-524, (IEEE) (2018)
  • G. Barthe, Th. Espitau, M. Gaboardi, B. Grégoire, J. Hsu, P.‑Y. Strub : “An Assertion-Based Program Logic for Probabilistic Programs”, Lecture Notes in Computer Science, Proceedings of ESOP 2018 - 27^th European Symposium on Programming, Thessaloniki, Greece, pp. 117-144, (Springer) (2018)
  • G. Barthe, S. Belaid, Th. Espitau, P.‑A. Fouque, B. Grégoire, M. Rossi, M. Tibouchi : “Masking the GLP Lattice-Based Signature Scheme at Any Order”, Eurocrypt 2018 - 37^th Annual International Conference on the Theory and Applications of Cryptographic Techniques, vol. 10821, Lecture Notes in Computer Science, Tel Aviv, Israel, pp. 354-384, (Springer) (2018)
• 2017
  • G. Barthe, Th. Espitau, B. Grégoire, J. Hsu, P.‑Y. Strub : “Proving expected sensitivity of probabilistic programs”, Proceedings of the ACM on Programming Languages, vol. 2 (POPL), pp. 1-29, (ACM) (2017)
  • G. Barthe, Th. Espitau, J. Hsu, T. Sato, P.‑Y. Strub : “Liftings for Differential Privacy”, ICALP 2017, Varsovie, Poland (2017)
  • G. Barthe, Th. Espitau, B. Grégoire, J. Hsu, P.‑Y. Strub : “Proving uniformity and independence by self-composition and coupling”, LPAR 2017 - International Conferences on Logic for Programming, Artificial Intelligence and Reasoning, LPAR 2017 - International Conferences on Logic for Programming, Artificial Intelligence and Reasoning, Maun, Botswana, pp. 19 (2017)
  • J.‑F. Biasse, Th. Espitau, P.‑A. Fouque, A. Gélin, P. Kirchner : “Computing generator in cyclotomic integer rings: A subfield algorithm for the Principal Ideal Problem in Ll∆Kl(1/2) and application to cryptanalysis of a FHE scheme”, Advances in Cryptology – EUROCRYPT 2017 36^th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part I, vol. 10210, Lecture Notes in Computer Science, Paris, France, pp. 60-88 (2017)
  • Th. Espitau, P.‑A. Fouque, B. Gérard, M. Tibouchi : “Side-Channel Attacks on BLISS Lattice-Based Signatures: Exploiting Branch Tracing against strongSwan and Electromagnetic Emanations in Microcontrollers”, CCS '17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, United States, pp. 1857-1874, (ACM) (2017)
• 2016
  • Th. Espitau, P.‑A. Fouque, B. Gérard, M. Tibouchi : “Loop abort Faults on Lattice-Based Fiat-Shamir & Hash’n Sign signatures”, 23^rd Conference on Selected Area In Cryptography, Saint John's, Canada (2016)
  • G. Barthe, Th. Espitau, L. María Ferrer Fioriti, J. Hsu : “Synthesizing Probabilistic Invariants via Doob’s Decomposition”, Computer Aided Verification 28^th International Conference, CAV 2016, Toronto, ON, Canada, July 17-23, 2016, Proceedings, vol. 9779, Lecture Notes in Computer Science, Toronto, Canada, pp. 43-61, (Springer) (2016)