Offre d'emploi Stagiaire F/H : Recherche d’équivalence dans Fp

Type de contrat : Convention de stage Niveau de diplôme exigé : Bac + 5 ou équivalent Fonction : Stagiaire de la recherche 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 algorithmes pour décider l’équivalence entre deux fonctions définies sur un corps fini de caractéristique impaire. 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 : La recherche d’équivalence entre fonctions est une question classique en informatique théorique et en cryptographie.

Elle consiste à déterminer si deux fonctions distinctes sont en réalité équivalentes selon une relation donnée.

Pour les fonctions définies sur un corps fini, on peut notamment considérer les équivalences linéaire, affine, affine étendue ou CCZ.

Par exemple, deux fonctions F et G définies sur un corps finis Fq sont équivalentes CCZ [CCZ98] si le graphe de la fonction F est équivalent affine au graphe de la fonction G. Ces équivalences ont été étudiées d’un point de vue mathématique, car elles permettent à la fois de classifier les fonctions sur un corps fini, et laissent invariantes des propriétés cryptographiques pertinentes (différentielles et linéaires). Plus récemment, un usage directement constructif de l’équivalence CCZ a été proposé dans un nouveau contexte, celui des systèmes de preuve à divulgation nulle de connaissance.

La fonction de hachage Anemoi [Bou+23] se base sur l’équivalence CCZ entre deux fonctions, l’une dite « Flystel ouvert », l’autre « Flystel fermé ».

La première permet de calculer H(a), la seconde de tester efficacement si b = H(a). L’optimisation de la recherche d’équivalence entre fonctions est donc un sujet important et d’actualité.

Contrairement aux fonctions de hachages traditionnelles qui manipulent des chaines de bits, les primitives adaptées aux preuves à divulgation nulle de connaissance, également appelées orientées arithmétisation, manipulent des éléments de grands corps finis.

Ce changement de perspective ouvre ainsi la porte a de nouvelles d’optimisations algorithmiques que nous explorerons lors de ce stage. Objectif : Alors que le nombre de conceptions orientées arithmétisation ne cesse d’augmenter, il est important de mieux comprendre les propriétés des opérations sous-jacentes et de concevoir des outils d’analyse adaptés. En particulier, l’aspect algorithmique de la recherche de relations d’équivalences (étant données F et G, décider si elles sont équivalentes) n’a été que très peu étudié.

Seul le cas des fonctions binaires a été considéré.

Un algorithme pour les équivalences linéaire et affine des permutations a été proposé dans [Bir+03].

Plus récemment, un algorithme probabiliste plus efficace a été proposé [Din18].

Pour les relations d’équivalence plus larges, ou pour les fonctions qui ne sont pas des permutations, les algorithmes connus fonctionnent seulement dans des cas particuliers (fonctions quadratiques, fonctions de degré maximal par exemple) [Din18; CCP21].

Ces algorithmes sont accessibles dans Sage via la bibliothèque SboxU [Ali+24]. A l’heure actuelle, aucun algorithme n’a été proposé pour les fonctions définies sur Fq lorsque q n’est pas une puissance de 2. Le premier objectif du stage sera de concevoir des algorithmes pour tester l’équivalence de fonctions sur des corps fini Fq , où q est une puissance d’un nombre premier p.

Ces derniers pourront s’inspirer des techniques existantes pour résoudre ce problème sur des corps binaires (i.e.

lorsque p = 2).

Les solutions proposées devront tirer profit des nouvelles perspectives offertes par l’usage de grands corps premiers. Le deuxième objectif sera d’implémenter ces algorithmes dans la version de développement de la bibliothèque SboxU.

Les languages utilisés pourront être C/C++ ou Python en fonction des contraintes de performances. Selon l’avancement du stage et l’efficacité des algorithmes conçus, ils pourront être utilisés pour étudier diverses équivalences, ou pour chercher des fonctions exhibant des caractéristiques intéressantes pour des constructions cryptographiques.

On pourra notamment s’intéresser à la structure en papillon [PUB16], dont le Flystel est inspiré, et classifier ses variantes. Equipe : La personne recrutée sera en lien avec Xavier Bonnetain (Chargé de recherche, Inria) et Virginie Lallemand (Chargée 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 et Léo Perrin.

SboxU.

2024.

url : https://github.com/lppcrypto/sboxU. [Bir+03] Alex Biryukov, Christophe De Canniére, An Braeken et Bart Preneel.

“A Toolbox for Cryptanalysis : Linear and Affine Equivalence Algorithms”.

In : EUROCRYPT 2003.

Sous la dir.

d’Eli Biham.

T.

2656.

LNCS.

Springer, Berlin, Heidelberg, mai 2003, p.

33-50.

doi : 10.1007/3-540-39200-9_3. [Bou+23] Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov et Danny Willems.

“New Design Techniques for Efficient Arithmetization-Oriented Hash Functions : Anemoi Permutations and Jive Compression Mode”.

In : CRYPTO 2023, Part III.

Sous la dir.

d’Helena Handschuh et Anna Lysyanskaya.

T.

14083.

LNCS.

Springer, Cham, août 2023, p.

507-539.

doi : 10.1007/978-3-031-38548-3_17. [CCP21] Anne Canteaut, Alain Couvreur et Léo Perrin.

Recovering or Testing Extended-Affine Equivalence.

Cryptology ePrint Archive, Report 2021/225.

2021.

url : https://eprint.iacr.org/2021/225. [CCZ98] Claude Carlet, Pascale Charpin et Victor Zinoviev.

“Codes, bent functions and permutations suitable for DES-like cryptosystems”.

In : Designs, Codes and Cryptography Vol.

15.2 (1998), p.

125-156. [Din18] Itai Dinur.

“An Improved Affine Equivalence Algorithm for Random Permutations”.

In : EUROCRYPT 2018, Part I.

Sous la dir.

de Jesper Buus Nielsen et Vincent Rijmen.

T.

10820.

LNCS.

Springer, Cham, 2018, p.

413-442.

doi : 10.1007/978-3-319-78381-9_16. [PUB16] Léo Perrin, Aleksei Udovenko et Alex Biryukov.

“Cryptanalysis of a Theorem : Decomposing the Only Known Solution to the Big APN Problem”.

In : CRYPTO 2016, Part II.

Sous la dir.

de Matthew Robshaw et Jonathan Katz.

T.

9815.

LNCS.

Springer, Berlin, Heidelberg, août 2016, p.

93-122.

doi : 10.1007/978-3-662-53008-5_4. Principales activités Principales activés : s'approprier l'état de l'art des algorithmes de recherche d'équivalence de fonctions en caractéristique paire adapter les outils ou en créer de nouveaux en caractéristique impaire implémenter ces algorithmes dans la bibliothèque SboxU Compétences Langues : bonne maîtrise de l'anglais. 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 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 Rémunération 4.50 €/heure Informations générales Thème/Domaine : Algorithmique, calcul formel et cryptologie Systèmes d'information (BAP E) Ville : Villers lès Nancy Centre Inria : Centre Inria de l'Université de Lorraine Date de prise de fonction souhaitée : 2026-03-09 Durée de contrat : 6 mois Date limite pour postuler : 2026-02-05 Attention: Les candidatures doivent être déposées en ligne sur le site Inria.

Le traitement des candidatures adressées par d'autres canaux n'est pas garanti. Consignes pour postuler Sécurité défense : Ce poste est susceptible d’être affecté dans une zone à régime restrictif (ZRR), telle que définie dans le décret n°2011-1425 relatif à la protection du potentiel scientifique et technique de la nation (PPST).

L’autorisation d’accès à une zone est délivrée par le chef d’établissement, après avis ministériel favorable, tel que défini dans l’arrêté du 03 juillet 2012, relatif à la PPST.

Un avis ministériel défavorable pour un poste affecté dans une ZRR aurait pour conséquence l’annulation du recrutement. Politique de recrutement : Dans le cadre de sa politique diversité, tous les postes Inria sont accessibles aux personnes en situation de handicap. Contacts Équipe Inria : CARAMBA Recruteur : Bouvier Clemence / clemence.bouvier@inria.fr L'essentiel pour réussir Prérequis : Connaissances en cryptographie, Bases de programmation. Qualités : aime apprendre et transmettre le résultat de ses recherches, se montre patient et résistant face à l'échec. A propos d'Inria Inria est l’institut national de recherche dédié aux sciences et technologies du numérique.

Il emploie 2600 personnes.

Ses 215 équipes-projets agiles, en général communes avec des partenaires académiques, impliquent plus de 3900 scientifiques pour relever les défis du numérique, souvent à l’interface d’autres disciplines.

L’institut fait appel à de nombreux talents dans plus d’une quarantaine de métiers différents.

900 personnels d’appui à la recherche et à l’innovation contribuent à faire émerger et grandir des projets scientifiques ou entrepreneuriaux qui impactent le monde.

Inria travaille avec de nombreuses entreprises et a accompagné la création de plus de 200 start-up.

L'institut s'efforce ainsi de répondre aux enjeux de la transformation numérique de la science, de la société et de l'économie. Avantages:
• Prise en charge du transport quotidien
• RTT
• Programme de formation