Doctorant F/H Analyse structurelle et algorithmique de fonctions cryptographiques définies sur des corps premiers

Contexte et atouts du poste

Contexte : Ce stage s'inscrit dans le cadre du projet Cryptanalyse du PEPR Cybersécurité et a pour objectif de concevoir des outils et algorithmes pour l'analyse de sécurité de fonctions définies sur des corps finis de caractéristiques impaires.

Atout : Des déplacements en conférence ou en séminaire, en France comme à l'étranger, seront à envisager pour diffuser les travaux réalisés. Les frais de déplacement et d'hébergement seront pris en charge dans la limite du barème en vigueur.

Mission confiée

Contexte et Motivation :

Les primitives cryptographiques symétriques ont historiquement été conçues dans un cadre booléen, où les fonctions considérées sont définies sur F2^n , où n est de l'ordre de 4 ou 8. Dans ce contexte, un large éventail d'outils mathématiques et algorithmiques a été développé pour analyser la sécurité de ces primitives, notamment via l'étude de propriétés différentielles, linéaires ou algébriques des fonctions sous-jacentes.
L'essor récent de protocoles tels que les systèmes de preuves à divulgation nulle de connaissance a conduit à l'introduction de nouvelles primitives symétriques, parmi lesquelles Poseidon [Gra+21], Anemoi [Bou+23] ou encore Rescue [Aly+20]. Ces primitives orientées arithmétisation, définies sur de grands corps finis, typiquement Fp pour des nombres premiers p de grande taille, reposent généralement sur des transformations polynomiales de faible degré, choisies de manière à minimiser le coøt arithmétique dans des circuits.
Ce changement de paradigme soulève de nombreuses questions en cryptanalyse. D'une part, les outils traditionnels ne se généralisent pas directement à des fonctions définies sur Fq avec q non binaire. D'autre part, la structure algébrique particulière de ces fonctions (faible degré, symétries, interactions spécifiques entre variables) peut induire des vulnérabilités nouvelles, encore largement inexplorées.

Objectifs :

Alors que le nombre de primitives orientées arithmétisation ne cesse de croître, il devient essentiel de mieux comprendre les propriétés des opérations sous-jacentes et de développer des outils d'analyse adaptés à ce cadre. Les objectifs principaux de cette thèse seront de développer un cadre unifié pour l'analyse des primitives orientées arithmétisation, et d'identifier de nouvelles classes de fonctions présentant des propriétés cryptographiques adaptées à ces applications.
Un premier axe de la thèse consistera à étudier plus finement les propriétés cryptographiques de primitives symétriques définies sur des corps premiers. On s'intéressera notamment à leur comportement différentiel et linéaire, ainsi qu'à la façon dont les outils classiques de cryptanalyse symétrique se généralisent dans ce contexte. L'objectif sera également de mieux comprendre les interactions entre différentes représentations ou transformations algébriques de ces fonctions, ainsi que les notions d'équivalence susceptibles de préserver certaines propriétés cryptographiques. L'étude visera également à mettre en évidence des invariants et phénomènes structurels permettant de mieux caractériser et analyser ces primitives.
Un deuxième axe portera sur le développement de méthodes de cryptanalyse adaptées à ce cadre. La cryptanalyse algébrique apparaît ici comme une approche particulièrement naturelle et prometteuse, dans la mesure où ces primitives sont généralement définies par des systèmes d'équations polynomiales de faible degré. Malgré des avancées significatives au cours des dernières années [Bar+24; Yan+24], de nombreuses questions restent ouvertes, en particulier concernant la complexité effective de la résolution de tels systèmes et l'exploitation de leur structure spécifique.
Une attention particulière sera enfin accordée à l'implémentation efficace des outils développés, afin de permettre leur expérimentation sur des instances de taille réaliste. Ces développements pourront par exemple s'appuyer sur des bibliothèques existantes telles que SboxU [Ali+24].

Equipe :

La personne recrutée sera en lien avec Clémence Bouvier (Chargée de recherche, Inria) et Pierre-Jean Spaenlehauer (Chargé de recherche, Inria). Elle sera pleinement intégrée à CARAMBA, une Équipe de Recherche Inria dont les membres s'intéressent à des questions d'algorithmiques liées à la cryptographie. Plus d'informations ici : https://www.inria.fr/fr/caramba .

Références :[Ali+24] Jens Alich, Jules Baudrin, Aurélien Boeuf, Xavier Bonnetain, Alain Couvreur, Mathias Joly, and Léo Perrin. SboxU. 2024. url: https://github.com/lppcrypto/sboxU .
[Aly+20] Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, and Alan Szepieniec. "Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols". In: IACR Trans. Symm. Cryptol. 2020.3 (2020), pp. 1-45. issn:2519-173X. doi: 10.13154/tosc.v2020.i3.1-45.
[Bar+24] Augustin Bariant, Aurélien Boeuf, Axel Lemoine, Irati Manterola Ayala, Morten Øygarden, Léo Perrin, and Håvard Raddum. "The Algebraic FreeLunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives".
In: CRYPTO 2024, Part IV. Ed. by Leonid Reyzin and Douglas Stebila. Vol. 14923. LNCS. Springer, Cham, Aug. 2024, pp. 139-173. doi: 10.1007/978-3-031-68385-5_5.
[Bou23] Clémence Bouvier. "Cryptanalysis and design of symmetric primitives defined over large finite fields". PhD thesis. Sorbonne Université, 2023.
[Bou+23] Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov, and Danny Willems. "New Design Techniques for Efficient Arithmetization-Oriented Hash Functions: Anemoi Permutations and Jive Compression Mode". In: CRYPTO 2023, Part III. Ed. by Helena Handschuh and Anna Lysyanskaya. Vol. 14083. LNCS. Springer, Cham, Aug. 2023, pp. 507-539. doi: 10.1007/978-3-031-38548-3_17.
[Gra+21] Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. "Poseidon: A New Hash Function for Zero-Knowledge Proof Systems". In: USENIX Security 2021. Ed. by Michael Bailey and Rachel Greenstadt. USENIX Association, Aug. 2021, pp. 519-535. url: https://www.usenix.org/conference/usenixsecurity21/presentation/grassi .
[Yan+24] Hong-Sen Yang, Qun-Xiong Zheng, Jing Yang, Quan feng Liu, and Deng Tang. "A New Security Evaluation Method Based on Resultant for Arithmetic-Oriented Algorithms". In: ASIACRYPT 2024, Part VII. Ed. by Kai-Min Chung and Yu Sasaki. Vol. 15490. LNCS. Springer, Singapore, Dec. 2024, pp. 457-489. doi: 10.1007/978-981-96-0941-3_15.

Principales activités

Principales activités :

• Étude bibliographique et analyse de la littérature récente sur les primitives orientées arithmétisation
• Étude de l'état de l'art des techniques de cryptanalyse en caractéristique paire
• Adaptation des outils ou développement de nouveaux en caractéristique impaire
• Rédaction et soumission d'articles scientifiques.
• Présentation des résultats dans des séminaires et conférences nationales et internationales.

• Restauration subventionnée
• Transports publics remboursés partiellement
• Congés: 7 semaines de congés annuels + 10 jours de RTT (base temps plein) + possibilité d'autorisations d'absence exceptionnelle (ex : enfants malades, déménagement)
• Possibilité de télétravail (après 6 mois d'ancienneté) et aménagement du temps de travail
• Équipements professionnels à disposition (visioconférence, prêts de matériels informatiques, etc.)
• Prestations sociales, culturelles et sportives (Association de gestion des œuvres sociales d'Inria)
• Accès à la formation professionnelle
• Sécurité sociale