CRYPTO – Jules Baudrin – L’auto-équivalence linéaire, un point de vue unifié sur les familles connues de fonctions APN
- Cet évènement est passé.
CRYPTO – Jules Baudrin – L’auto-équivalence linéaire, un point de vue unifié sur les familles connues de fonctions APN
21 février / 11:00 - 12:00
Les fonctions APN (Almost Perfect Nonlinear) sont les fonctions qui offrent une résistance optimale à la cryptanalyse différentielle. Étudiées depuis plus de 30 ans, elles posent encore un grand nombre de problèmes ouverts. Le plus important est sans aucun doute le « grand problème APN » : existe-t-il une bijection APN de GF(2^n) dans lui-même quand n est pair et strictement supérieur à 6 ?
Il a longtemps été conjecturé que les bijections APN n’existaient pas en dimension n paire, jusqu’à l’identification par Dillon en 2009 d’une bijection APN de GF(2^6) dans la classe d’équivalence CCZ d’une fonction quadratique. Il s’agit cependant du seul exemple (à équivalence près) connu à ce jour.
Naturellement, un grand nombre de travaux a tenté de généraliser la construction de Dillon, en cherchant de nouvelles fonctions APN en dimension paire puis en parcourant leur classe d’équivalence CCZ. Ces recherches incluent des travaux mathématiques qui définissent des familles de fonctions quadratiques APN par une forme polynomiale instantiable pour presque toutes valeurs de n, mais aussi des travaux algorithmiques permettant de trouver un grand nombre de fonctions APN quadratiques pour de petites valeurs de n, typiquement 8 ou 10. Parmi ces derniers, une idée récente consiste à rechercher des fonctions APN uniquement parmi les fonctions linéairement auto-équivalentes, i.e. pour lesquelles il existe deux bijections linéaires A, B telles que B o F o A = F.
Dans un récent travail collaboratif avec Anne Canteaut et Léo Perrin, nous avons montré que, malgré des techniques très diverses, l’immense majorité des familles infinies de fonctions APN connues partagent les mêmes propriétés structurelles, puisqu’elles sont elles aussi, (à équivalence près), linéairement auto-équivalentes. Après des rappels contextuels et une présentation détaillée de la boîte à outils d’analyse de fonctions booléennes, nous aborderons donc ce point de vue unifié, ce qu’il dit de notre compréhension actuelle des fonctions APN, mais aussi les problèmes et perspectives ouverts (ou réouverts) par notre travail.
CRYPTO – Jules Baudrin – L’auto-équivalence linéaire, un point de vue unifié sur les familles connues de fonctions APN