Pourquoi la non-linéarité de cette fonction booléenne est-elle évaluée à $\frac12$?

Question

J'utilise la méthode présentée dans cet article pour trouver la non-linéarité de la fonction

$$ f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \\ f(x) = x$$

La table de vérité est $f = [0 \space \space 1]$. Maintenant, j'ai lu dans le journal de Terry Ritter que

La non-linéarité est le nombre de bits qui doivent changer dans la table de vérité d'une fonction booléenne pour atteindre la fonction affine la plus proche.

Cela signifie que la valeur de non-linéarité doit être un nombre entier.

L'algorithme pour calculer la non-linéarité consiste d'abord à utiliser la transformation rapide de Walsh pour trouver le spectre de Walsh, puis à utiliser la formule

$$Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$

où le spectre de Walsh est calculé en multipliant la table de vérité de la fonction par la matrice Hadamard correspondante.

Donc, depuis $k = 1$, nous utilisons la matrice Hadamard de taille $2^1$ donnant le spectre de Walsh suivant:

$$ \begin{bmatrix}0 & 1\end{bmatrix} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} = \begin{bmatrix}1 & -1\end{bmatrix} \implies \max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| = |-1| = 1 $$

Donc

$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12$$

Qu'est-ce que je rate?

---

Au cas où les liens seraient morts, les articles liés sont:

1. Calcul de la non-linéarité des fonctions booléennes avec la transformation de Walsh-Hadamard par Pedro Miguel Sosa
2. Mesure de la non-linéarité des fonctions booléennes par transformation de Walsh par Terry Ritter

Answer 1

Dans cette formulation, vous devez convertir la plage de sortie de votre fonction en $\{-1,+1\}$ via $$f`(x)=(-1)^{f(x)}$$ et appliquer le Walsh Hadamard à la nouvelle fonction $f`(x)$. L'utilisation de la formulation zéro un signifie que vous êtes décalé par une constante en fonction du nombre de variables puisque

$$ (-1)^u=1-2u $$ pour $u\in \{0,1\}.$

Voir ma réponse ci-dessous sur les fonctions booléennes et la cryptographie, cela peut être utile compte tenu de vos questions récentes.

Comment les fonctions booléennes sont-elles utilisées en cryptographie?

Answer 2

En plus de la réponse de Kodlu, après avoir soigneusement relu les articles, j'ai pu comprendre. Points clés à noter:

1. Si nous utilisons la transformation rapide de Walsh sur des fonctions booléennes consistant en $\{0,1\}$ alors la formule de la non-linéarité est

... la moitié du nombre de bits de la fonction, moins la valeur absolue de la distance inattendue.

C'est $$ Nl(f) = \dfrac12 \cdot 2^k - \max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)|\\ = 2^{k-1} - \max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$

Par conséquent, pour la question dans le message d'origine, nous avons

$$Nl(f) = 2^{0} - |1| = 0$$

Alternativement, page 20 ici ( lien alt ) suggère de procéder comme suit: Après avoir trouvé la transformation Fast Walsh,

1. Ajouter $2^{k-1}$à chaque entrée de la ligne sauf la première entrée. Cela nous donne une nouvelle ligne, appelez-la$FHT'$

2. Si une entrée en moins de $2^{k-1}$il reste inchangé. Sinon, si une entrée de$FHT'$ est supérieur à $2^{k-1}$ puis soustrayez-le de $2^k$.

3. Enfin, la non-linéarité est le plus petit de ces éléments ajustés.

2. Si nous utilisons la transformation rapide de Walsh sur des fonctions booléennes consistant en $\{1,-1\}$ alors la formule de la non-linéarité est

$$ Nl(f) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$

Car

Utiliser des valeurs réelles $\{1,-1\}$ double la magnitude et change le signe des résultats FWT

La source