Jeudi 11 mai 2017 à 16h00 en salle C48
Sébastien Duval (INRIA)
Titre : Étude d'une Généralisation de la Boîte-S de Dillon
Résumé :
Les fonctions non-linéaires, aussi appelées Boîtes-S, sont des composants essentiels pour la construction de primitives de cryptographie symétrique. La résistance d’une Boîte-S est généralement mesurée par plusieurs paramètres cryptographiques des fonctions Booléennes : l’uniformité différentielle, la non-linéarité et le degré algébrique par exemple.
L’uniformité différentielle mesure la résistance aux attaques différentielles : la résistance est d’autant meilleure que l’uniformité différentielle est basse. La meilleure valeur atteignable pour l’uniformité différentielle est 2 et les fonctions qui atteignent cette valeur sont appelées APN.
Il a longtemps été conjecturé qu’il n’existait pas de permutation APN sur un nombre pair de variables.
En 2009, Dillon et al. [BDMW10] ont prouvé l’existence de permutations APN 6 variables en donnant un exemple. Malgré ce résultat, aucun autre exemple de permutation APN sur un nombre pair de bits n’existe l’heure actuelle.
En 2016, Perrin et al. [PUB16] ont identifié une structure derrière la permutation de Dillon et al. Ils ont baptisé cette structure un Papillon, opérant sur (4k + 2) variables. Leur étude prouve que les Papillons ont une uniformité différentielle d’au plus 4, et sont APN lorsque k = 1 (le cas de 6 variables). Deux questions ouvertes ́emergent de leurs travaux, savoir la valeur exacte de la non-linéarité des Papillons et si la structure de Papillon permet de construire des permutations
APN sur plus de 6 variables.
Dans ce travail, nous généralisons les Papillons. En restreignant notre étude aux fonctions de degré 3, qui incluent la permutation de Dillon, nous pouvons utiliser les propriétés des fonctions Booléennes de degré 3 pour étudier les propriétés cryptographiques de la construction et résoudre les deux problèmes de [PUB16].
Nous prouvons que tous les Papillons généralisés atteignent la meilleure non-linéarité connue.
Malheureusement, nous prouvons également que la permutation de Dillon est (équivalence affine près) la seule permutation APN de cette famille, impliquant que les autres permutations ont une uniformité différentielle de 4. Quoi qu’il en soit, ces nouvelles permutations ont une excellente résistance et une structure simple qui permet une bonne ́etude et une implémentation peu coûteuse.
[BDMW10] K.A. Browning, J.F. Dillon, M.T. McQuistan, and A.J. Wolfe. An APN permutation in dimension six.
In Finite Fields : Theory and Applications - FQ9, volume 518 of Contemporary Mathematics, pages 33–42. AMS, 2010.
[PUB16] Léo Perrin, Aleksei Udovenko, and Alex Biryukov. Cryptanalysis of a theorem : Decomposing the only known solution to the big APN problem.
In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016, Part II, volume 9815, pages 93–122. Springer, 2016.