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], Anemoi [Bou] ou encore Rescue [Aly]. 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; Yan], 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].

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 : Références :

[Ali] Jens Alich, Jules Baudrin, Aurélien Boeuf, Xavier Bonnetain, Alain Couvreur, Mathias Joly, and Léo Perrin. SboxU. 2024. url: .
[Aly] 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 , pp. 1–45. issn:2519-173X. doi: 10.13154/tosc.v2020.i3.1-45.
[Bar] 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] 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] 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:

Principales activités

Principales activités :

Compétences

Langues : bonne maîtrise de l'anglais afin de pouvoir présenter les résultats par écrit et lors de communications orales.

Compétences relationnelles : La personne recrutée sera amenée à communiquer régulièrement avec ses encadrants. Il est attendu qu'elle s'intègre et participe activement à la vie de l'équipe.

Avantages

Rémunération

2300 € brut/mois