Codage énumératif et génération aléatoire des fonctions 1-résilientes

Le codage énumératif est un problème issu de la théorie de l’information. Il consiste à associer à chaque objet d’un ensemble fini d’objets un numéro et inversement de pouvoir retrouver l’objet correspondant à partir d’un numéro. Nous verrons comment utiliser un codage énumératif pour effectuer un tirage uniforme sur cet ensemble.

Le codage énumératif proposé dans cet exposé se fera sur des classes de fonctions booléennes constituées à partir d’un critère très important dans ce domaine, notamment en vue d’applications en cryptographie : la corrélation d’ordre 1. Nous pourrons en particulier le définir pour la classe des fonctions 1-résilientes. Nous verrons quelles sont les limites de la méthode et discuterons des possibilités de l’utiliser en cryptographie.