Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 6 Mars 2001

Les représentations des fonctions booléennes et leur propriétés cryptographiques

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr