Claude Carlet (GREYC, PARIS VIII et INRIA)

Une fonction booléenne est une application de l’ensemble des mots binaires de longueur n (considéré comme un espace vectoriel de dimension n sur le corps à deux éléments) et à valeurs 0 et 1. Cette étude se situe dans le cadre de la cryptographie symétrique mais elle est aussi liée à l’étude des codes correcteurs d’erreurs, via les codes de Reed-Muller.

Je rappellerai brièvement les représentations usuelles des fonctions booléennes qui jouent un rôle en cryptographie (table de vérité, forme algébrique normale, table de vérité restreinte, représentation de Fourier) et j’insisterai un peu plus sur la forme numérique normale, récemment introduite. J’étudierai, en relation avec ces représentations, les différents critères de complexité qui nous intéressent en cryptographie (non-linéarité, nombre de termes de la forme algébrique normale, non-normalité). Je rappellerai ce qu’on saitconcernant la non-linéarité des fonctions booléennes générales et j’introduirai de nouveaux résultats concernant chacun des deux autres critères.

Puis je restreindrai mon étude aux fonctions résilientes, qui interviennent dans les schémas de chiffrement symétriques par fonctions de combinaison. J’établirai une borne sur leur non-linéarité. Je montrerai à cette occasion l’efficacité de la forme numérique normale.