Fonction booléenne

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Une fonction booléenne est une fonction de $\mathbb{F}^n$ dans $\mathbb{F}$ où $\mathbb{F}$ désigne le corps fini à 2 éléments.

En fait, les fonctions booléennes sont simplement un autre nom des fonctions logiques. Toutefois, lorsque l'on s'attache aux propriétés algébriques de ces fonctions, l'appellation fonction booléenne est la plus utilisée.

Les fonctions booléennes, ou plus précisément leurs propriétés, interviennent notamment en cryptologie dans les boîtes-S, ainsi que dans les chiffrements par flot -- fonction de filtrage ou de combinaison des registres à décalage.

Sommaire

1 Propriétés
2 Outil d'étude : la transformée de Fourier
- 2.1 Cas d'un groupe abélien fini
- 2.2 Application à

[modifier] Propriétés

[modifier] Forme algébrique normale

Les corps finis et les polynômes interpolateurs de Lagrange conduisent rapidement à une propriété fondamentale des fonctions booléennes : la représentation dite « forme algébrique normale » (algebraic normal form ou ANF). Toute fonction booléenne peut s'écrire comme un polynôme en $n$ variables à coefficients dans $\mathbb{F}$ . Cependant, différents polynômes de $\mathbb{F}[X_0,...,X_{n-1}]$ donnent la même fonction. Par exemple, $X_0^2$ et $X_0^3$ donnent bien la même valeur lorsqu'ils sont évalués sur un élément de $\mathbb{F}^n$ . Pour obtenir une représentation unique, il faut considérer les éléments de l'anneau quotient, soit :

$\mathbb{F}[X_0,...,X_{n-1}]/(X_0^2+X_0,...,X_{n-1}^2+X_{n-1})$

Autrement dit, une fonction booléenne peut être représentée de manière unique par un polynôme de la forme :

$P(X_0,...,X_{n-1}) = \sum_{(u_0,...,u_{n-1})\in\mathbb{F}^n} a_u\prod_{i=0}^{n-1}X^{u_i}$

On pose fréquemment $u=(u_0,...,u_{n-1})~$ , $X=(X_0,...,X_{n-1})~$ et $X^u=\prod_{i=0}^{n-1}X^{u_i}$ , permettant l'écriture compacte :

$P(X)=\sum_{u\in\mathbb{F}^n} a_uX^u$ .

La notion de degré d'une fonction booléenne est alors évidente, il s'agit du degré maximal des monômes de son ANF.

[modifier] Linéarité et Non-linéarité

Les fonctions de degré 1 sont appelées les fonctions affines. En fait, ce sont des formes affines de l'espace vectoriel $\mathbb{F}^n$ -- vu comme espace sur le corps $\mathbb{F}$ . Ce sont bien évidemment les fonctions les plus simples (hormis les constantes). Il a fini par apparaître que « ressembler » à une fonction linéaire était une propriété pouvant être exploitée en cryptanalyse. La ressemblance en question se base sur le nombre de fois où deux fonctions prennent la même valeur, il s'agit de la distance de Hamming :

$d_H(f,g) = \#\{u\in\mathbb{F}^n : f(u)\neq g(u)\}$

Les cryptographes utilisent le terme de non-linéarité pour parler de la distance d'une fonction booléenne à l'ensemble $\mathcal{A}$ des fonctions affines :

$\mathcal{N}(f)=\min \{d_H(f,g) : g\in \mathcal{A}\}$

L'intérêt de cette notion est de quantifier l'erreur commise si on remplace la fonction $f$ par une fonction affine : dans le meilleur des cas, on se « trompe » $\mathcal{N}(f)$ fois sur $2 n$ si $n$ est le nombre de variables.

On montre, en utilisant la transformée de Fourier, que la non-linéarité d'une fonction booléenne est au plus de

$\mathcal{N}(f)\le 2^{n-1}-2^{\frac{n}{2}-1}$

Lorsque $n$ est impair, cette borne supérieure est atteinte, on parle alors de fonction courbe.

Précisons que l'ensemble des fonctions affines a une importance particulière en théorie des codes correcteurs, au point qu'il possède un nom, le code de Reed-Muller d'ordre $1$ (en $n$ variables). L'ordre est bien entendu le degré maximal des fonctions. Ainsi, le code de Reed-Muller d'ordre $r~$ en $n~$ , usuellement noté $\mathrm{RM}(r,n)~$ est l'ensemble des fonctions en $n~$ variables de degré au plus $r~$ . Dans le contexte de la théorie des codes, la non-linéarité maximale se trouve correspondre au « rayon de recouvrement » du code $\mathrm{RM}(1,n)~$ , c'est-à-dire, la distance maximale entre un mot binaire de longueur $2 n$ et un mot du code.

[modifier] Résilience

à faire

[modifier] Outil d'étude : la transformée de Fourier

La transformation de Fourier, appliquée aux fonctions booléennes, se révèle être un moyen très puissant pour explorer les différentes propriétés de ces objets. Elle est, par exemple, fréquemment utilisée pour étudier des propriétés cryptographiques comme la non-linéarité maximale. On la retrouve également dans des aspects plus appliquées : l'existence d'algorithmes de calcul de la transformée de Fourier de type FFT sert à décoder efficacement les codes de Reed et Muller. On trouvera dans la suite une presentation générale de la transformation de Fourier dans le cas des groupes abéliens finis qui est ensuite particularisée pour le cas des fonctions booléennes. Pour le cas général des groupes topologiques, voir la dualité de Pontryagin.

[modifier] Cas d'un groupe abélien fini

[modifier] Caractère et groupe dual

De manière générale, on peut définir une transformation de Fourier sur un groupe $\mathcal G$ en utilisant la notion de caractère. Un caractère $χ$ est un morphisme de $\mathcal G$ dans $\mathbb U$ , le groupe des racines de l'unité du corps des nombres complexes $\mathbb C$ . Si $\mathcal G$ est noté additivement, on a donc

$\chi(a+b)=\chi(a)\cdot\chi(b)$ .

L'ensemble des caractères de $\mathcal G$ peut être muni d'une structure de groupe en utilisant la multiplication entre applications

$(\chi\cdot\chi')(a)=\chi(a)\cdot\chi'(a)$ pour

χ,χ'

des caractères et

a

un élément de $\mathcal G$ .

On appele ce groupe le groupe dual de $\mathcal G$ et on le notera $\hat {\mathcal G}$ .

[modifier] Définition de la transformée de Fourier

Lorsque $\mathcal G$ est abélien et fini, son dual lui est isomorphe. On appele alors transformée de Fourier d'une application de ${\mathcal G}$ dans $\mathbb C$ et on note ${\mathcal F}(f)$ , la fonction :

${\mathcal F}(f)(\chi)=\sum_{x\in{\mathcal G}}f(x)\chi(x)$

C'est donc une fonction de $\hat{\mathcal G}$ dans $\mathbb C$ . La transformation inverse est obtenue par

${\mathcal F}^{-1}(g)(x)=\frac{1}{|{\mathcal G}|}\sum_{\chi\in\hat{\mathcal G}}g(\chi)\chi(-x)$

où cette fois, $g$ va de $\hat{\mathcal G}$ dans $\mathbb C$ et ${\mathcal F}^{-1}(g)$ de ${\mathcal G}$ dans $\mathbb C$ . On démontre que c'est effectivement la transformation inverse, c'est-à-dire que l'on a ${\mathcal F}^{-1}({\mathcal F}(f)) =f$ en commençant par démontrer les relations d'orthogonalité

$\sum_{\chi\in\hat{\mathcal G}} \chi(x)= \left\{\begin{matrix} 0, & \mbox{si }x\neq 0 \\ |{\mathcal G}|, & \mbox{si }x=0 \end{matrix}\right.$

$0\in{\mathcal G}$ étant le neutre de ${\mathcal G}$ .

[modifier] Formule de Poisson

Dans ce cadre, on a toujours une formule de Poisson. Pour la présenter, il faut introduire la notion de groupe orthogonal d'un sous-groupe ${\mathcal H}\subset{\mathcal G}$

${\mathcal H}^\bot=\{\chi\in\hat{\mathcal G} : \forall a\in{\mathcal H}, \chi(a)=1 \}$

L'ensemble ${\mathcal H}^\bot$ est un sous-groupe de $\hat{\mathcal G}$ , le groupe des caractères de ${\mathcal G}$ . Il est donc muni de la multiplication des applications et nous le noterons donc de manière multiplicative. La notation usuelle $\Psi{\mathcal H}^\bot$ désignera donc l'ensemble des éléments de la forme $Ψχ$ pour $\chi\in{\mathcal H}^\bot$ . On gardera en mémoire que le groupe ${\mathcal H}$ est, lui, noté additivement, puisque c'est un sous-groupe de ${\mathcal G}$ . C'est donc la notation $b+{\mathcal H}$ que nous utiliserons dans ce cas.

On peut alors écrire une première version de la formule de Poisson sous la forme relativement simple

$\sum_{\chi\in{\mathcal H}^\bot} {\mathcal F}(f)(\chi)\chi(-b) = |H^\bot| \cdot \sum_{x\in b+{\mathcal H}} f(x)$

avec ${\mathcal H}\subset{\mathcal G}$ un sous-groupe, $b\in{\mathcal G}$ .

De cette formulation, en l'appliquant à $f Ψ$ , pour $f:{\mathcal G}\to {\mathbb C}$ et $\Psi\in\hat{\mathcal G}$ un caractère, on obtient une version équivalente :

$\sum_{\chi\in\Psi{\mathcal H}^\bot} {\mathcal F}(f)(\chi)\chi(-b)= \Psi(-b) |H^\bot| \cdot \sum_{x\in b+{\mathcal H}} f(x)\Psi(x)$

[modifier] Application à $\mathbb{F}^n$

[modifier] Formes des caractères et isomorphisme avec le dual

Dans le cas qui nous interesse, commençons par prendre ${\mathcal G}=<\{0,1\},+>$ . Il est assez simple de voir qu'il n'y a que deux caractères possibles :

χ 0 (a) = 1

χ 1 (a) = ( - 1) a

Comme $\widehat{{\mathcal G}^n}$ est isomorphe à ${{\mathcal G}^n}$ , on en déduit la forme des caractères de ${{\mathcal G}^n}$

$\chi(x_0,...,x_{n-1}) = \chi_{y_0}(x_0)\cdots\chi_{y_{n-1}}(x_{n-1}) = {(-1)}^{\sum x_i\cdot y_i}$

où $x_i\in\{0,1\}$ et $\chi_{y_j}\in\hat {\mathcal G}=\{\chi_0,\chi_1\}$ . Assez naturellement, on prendra $y_j\in\{0,1\}$ de tel sorte que $\chi_{y_j}=\chi_0$ si et seulement si $y j = 0$ et le caractère précédent sera alors noté $χ y$ , où $y=(y_0,...,y_{n-1})\in{\mathcal G}^n$ .

Il est facile, dans le cas de $\mathbb{F}^n$ , d'expliciter un isomorphisme entre $\mathbb{F}^n$ et son dual $\widehat{\mathbb{F}^n}$

$y \mapsto \chi_y$

On utilisera cet isomorphisme pour identifier $\mathbb{F}^n$ et $\mathbb{F}^n$ , partout où cela aidera. Toutefois, nous allons commencé par écrire rigoureusement la transformée de Fourier d'une application $f$ et nous changerons ensuite cette définition pour prendre en compte notre isomorphisme.

[modifier] Transformation de Fourier

En reprenant la notation usuelle ${\mathbb F}=<\{0,1\},+>$ , la transformée de Fourier est alors définie rigoureusement par

${\mathcal F}(f)(\chi)=\sum_{x\in{\mathbb{F}^n}}f(x)\chi(x)$

La fonction ${\mathcal F}(f)$ est donc de $\widehat{{\mathbb F}^n}$ vers ${\mathbb C}$ . Toutefois, pour tout $χ$ , il existe $y\in{\mathbb F}^n$ tel que $χ = χ y$ . On fera donc l'abus d'identifier la transformée ${\mathcal F}(f)$ définie sur $\widehat{{\mathbb F}^n}$ et l'application $\hat f$ définie sur ${\mathbb F}^n$ par

$\hat f (y)={\mathcal F}(f)(\chi_y)=\sum_{x\in{\mathbb{F}^n}}f(x){(-1)}^{x\cdot y}$

où ${x\cdot y}$ est la somme ${\sum x_i\cdot y_i}$ .

On opère le même type d'identification pour la transformée inverse qui devient

${\hat f}^{-1}(x)=\frac{1}{2^n} \hat f(x)$

On voit donc que l'un des intérêts de cette identification est d'avoir la transformation de Fourier et son inverse qui agissent sur les mêmes objets : des fonctions de $\mathbb{F}^n$ dans ${\mathbb C}$ .

[modifier] Formule de Poisson

Un autre intérêt de l'identification de $\mathbb{F}^n$ et de son dual, et non moins agréable que celui évoqué précédemment, est de simplifier considérablement la formule de Poisson. En effet, on obtient alors

$\sum_{u\in a+{\mathcal H}^\bot} {\hat f}(u) {(-1)}^{u\cdot b}= {(-1)}^{a\cdot b} |H^\bot| \cdot \sum_{u\in b+{\mathcal H}} f(u)(-1)^{a\cdot u}$

On remarquera que ${\mathcal H}^\bot$ s'identifie naturellement à $\{z\in\mathbb{F}^n : \forall x\in H, z\cdot x=0 \}$ . C'est ce qui est fait dans la formule ci-dessus, passant ainsi d'une notation multiplicative pour ${\mathcal H}^\bot$ à une notation additive (on a également utilisé $b = - b$ dans le cas de $\mathbb{F}^n$ ). On vérifira également que ${\mathcal H}$ et ${\mathcal H}^\bot$ sont des espaces vectoriels sur $\mathbb{F}$ .