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.