|
Les fonctions booléennes sont très utilisées en cryptographie et en codage. On les retrouve, par exemple, dans la génération pseudo-aléatoire de nombres, les tables de registres, la construction de certains blocs de chiffrement (le DES entre autre),... Dans ces différents domaines les fonctions doivent avoir de bonnes propriétés, comme la non-linéarité et la facilité d'implémentation. Nous n'avons pas beaucoup d'outils pour les étudier, cependant, dans un article [1], Claude Carlet a introduit recémment le principe de séquences couvrantes comme nouveau moyen d'étude.
Nous étudions ici les fonctions booléennes sur . Dans son article [1], Claude Carlet conjecture qu'une fonction possède beaucoup de séquences couvrantes. Afin de réduire notre champs d'étude, nous avons donc définit un ``pseudo-ordre'' pour les séquences et regarder pour cet ordre le comportement de séquences couvrantes dites minimales. L'un de nos objectifs devenait ainsi la découverte de:
On connaît déjà tout sur les fonctions booléennes de degré et , et on voudrait maintenant savoir si celles de degré 3 ont de bonnes propriétés cryptographiques. En étudiant les séquences couvrantes, nous cherchons à savoir s'il existe une différence entre les fonctions booléennes de degré et les autres.
Nous nous sommes penchés sur les articles de Hou et Berlekamp traitant de la classification des fonctions booléennes afin de faciliter les calculs et d'augmenter notre champs d'étude de ces fonctions. Nous avons dû adapter et compléter certains résultats de ces articles afin qu'ils correspondent à nos besoins. Cette classification nous a permis de réaliser les tests sur les fonctions à 5 variables.
Un long travail d'implémentation a également été effectué, permettant ainsi de conjecturer certains résultats, et de nous mettre sur la voix de théorèmes. Un ensemble de bibliothéques d'opérations sur les fonctions boolénnes et les séquences couvrantes a été réalisé. Ce travail peut être réutilisé dans d'autres programmes.
|
abstract