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 2007

Enumération de fonctions booléennes 1-résilientes

par Jean-Marie Le Bars (GREYC)

Les fonctions interviennent depuis longtemps en cryptographie comme primitives cryptographiques, par exemple comme fonctions de combinaison et de filtrage dans les schémas de chiffrement à flots. Elles doivent satisfaire différents critères (degré algébrique, non-linéarité, k-résilience), mais il faut souvent trouver un compromis entre ces propriétés car elles induisent des incompatibilités partielles.

Nous nous intéressons ici au critère d'immunité aux corrélations. Notre objectif est de classifier les fonctions booléennes et de mesurer la représentativité d'une fonction selon ce critère.

Nous verrons une méthode pour coder les fonctions booléennes qui permet de classifier les fonctions selon leur distance aux fonctions sans corrélation d'ordre 1. Ce codage a de bonnes propriétés algorithmiques, nous disposons ainsi des premiers algorithmes efficaces pour énumérer et générer des fonctions 1-résilientes. Il permet aussi d'obtenir les premières bornes inférieures significatives du nombre de fonctions 1-résilientes.

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