Description du sujet de thèse

La cryptographie vise à sécuriser les connexions, les données, et plus généralement les systèmes d'information. Cependant, la cryptographie ajoute un coût important sur les infrastructures système et réseau. Deux problématiques majeures se distinguent alors : (1) réduire les coûts autant que possible et (2) obtenir et vérifier la sécurité.

Dans cette thèse, l'objectif est d'utiliser l'algorithmique et de développer des outils pour progresser sur ces problématiques. Une attention particulière sera portée sur les composants fondamentaux des algorithmes cryptographiques, à savoir la boîte-S et la matrice de diffusion, dont les propriétés et le coût déterminent la sécurité et le coût de la cryptographie en général.

Ceci implique d'utiliser plusieurs approches :

des approches mathématiques
par classes d'équivalences de fonctions [LP07,BL08,Saa11]
par l'identification de structures algébriques comme les "length-doubling structures" [LW14,CDL15,BDD+20]
par des probabilités et des heuristiques
des approches algorithmiques
par découpage des fonctions cryptographiques en morceaux simples (par exemple, des morceaux linéaires et d'autres non-linéaires) [BDD+20]
par des parcours de graphes
par des algorithmes d'optimisation [Saa11, BDD+20, DL18]
des approches par résolution de contraintes
outils de Mixed Integer Linear Programming (MILP) : contraintes sous forme d'inéquations linéaires [DL22]
outils de programmation par contraintes (CP) : contraintes sous forme de bornes sur les domaines des variables [PT22]
outils de SATisfiabilité (SAT) : contraintes sous forme de clauses logiques [Saa11,BDD+20]

Cette thèse implique aussi du travail d'implémentation d'algorithmes optimisés. En particulier, les langages C et C++ seront nécessaires pour une grosse part de l'implémentation. L'implémentation devra aussi faire un usage intelligent des ressources de la machine (temps, mémoire, nombre de coeurs).

[BDD+ 20] Begül Bilgin, Lauren De Meyer, Sébastien Duval, Itamar Levi, and François-
Xavier Standaert. Low and depth and efficient inverses: a guide on s-
boxes for low-latency masking. IACR Transactions on Symmetric Cryptology,
2020(1):144–184, May 2020.

[BL08] Marcus Brinkmann and Gregor Leander. On the classification of APN functions
up to dimension five. Des. Codes Cryptogr., 49(1-3):273–288, 2008.

[CDL15] Anne Canteaut, Sébastien Duval, and Gaëtan Leurent. Construction of
lightweight s-boxes using feistel and MISTY structures. In Orr Dunkelman
and Liam Keliher, editors, Selected Areas in Cryptography - SAC 2015 - 22nd
International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised
Selected Papers, volume 9566 of Lecture Notes in Computer Science, pages
373–393. Springer, 2015.

[JPST17] Jérémy Jean, Thomas Peyrin, Siang Meng Sim, and Jade Tourteaux. Optimiz-
ing implementations of lightweight building blocks. IACR Trans. Symmetric
Cryptol., 2017(4):130–168, 2017.

[LP07]Gregor Leander and Axel Poschmann. On the classification of 4 bit s-boxes.
In Claude Carlet and Berk Sunar, editors, Arithmetic of Finite Fields, First
International Workshop, WAIFI 2007, Madrid, Spain, June 21-22, 2007, Pro-
ceedings, volume 4547 of Lecture Notes in Computer Science, pages 159–176.
Springer, 2007.

[LW14]Yongqiang Li and Mingsheng Wang. Constructing s-boxes for lightweight
cryptography with feistel structure. In Lejla Batina and Matthew Robshaw,
editors, Cryptographic Hardware and Embedded Systems - CHES 2014 - 16th International Workshop, Busan, South Korea, September 23-26, 2014. Pro-
ceedings, volume 8731 of Lecture Notes in Computer Science, pages 127–146.
Springer, 2014.

[LWF+ 22] Qun Liu, Weijia Wang, Yanhong Fan, Lixuan Wu, Ling Sun, and Meiqin Wang.
Towards low-latency implementation of linear layers. IACR Trans. Symmetric
Cryptol., 2022(1):158–182, 2022.

[MB19] Lauren De Meyer and Begül Bilgin. Classification of balanced quadratic
functions. IACR Trans. Symmetric Cryptol., 2019(2):169–192, 2019.

[Saa11] Markku-Juhani O. Saarinen. Cryptographic analysis of all 4 × 4-bit s-boxes.
In Ali Miri and Serge Vaudenay, editors, Selected Areas in Cryptography - 18th
International Workshop, SAC 2011, Toronto, ON, Canada, August 11-12, 2011,
Revised Selected Papers, volume 7118 of Lecture Notes in Computer Science,
pages 118–133. Springer, 2011.

[Sto16] Ko Stoffelen. Optimizing s-box implementations for several criteria using SAT
solvers. In Thomas Peyrin, editor, Fast Software Encryption - 23rd International
Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected
Papers, volume 9783 of Lecture Notes in Computer Science, pages 140–160.
Springer, 2016.

[DL18] Duval, S., & Leurent, G. (2018). MDS Matrices with Lightweight Circuits. IACR Transactions on Symmetric Cryptology, 2018(2), 48–78. https://doi.org/10.13154/tosc.v2018.i2.48-78

[DL22] Derbez, P., & Lambin, B. (2022). Fast MILP Models for Division Property. IACR Transactions on Symmetric Cryptology, 2022(2), 289–321. https://doi.org/10.46586/tosc.v2022.i2.289-321

[PT22] Peyrin, T., & Tan, Q. Q. (2022). Mind Your Path: On (Key) Dependencies in Differential Characteristics. IACR Transactions on Symmetric Cryptology, 2022(4), 179–207. https://doi.org/10.46586/tosc.v2022.i4.179-207

[DR20] Joan Daemen and Vincent Rijmen.The Design of Rijndael. Springer BerlinHeidelberg, 2020

Contexte de travail

Financement du projet ANR OREO. Les résultats seront intégralement publiés et les codes afférents seront publiés sur git.

Le poste se situe dans un secteur relevant de la protection du potentiel scientifique et technique (PPST), et nécessite donc, conformément à la réglementation, que votre arrivée soit autorisée par l'autorité compétente du MESR.