Warum wird die Nichtlinearität dieser Booleschen Funktion ausgewertet? $\frac12$?

Question

Ich verwende die in diesem Artikel vorgestellte Methode , um die Nichtlinearität der Funktion zu ermitteln

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

Die Wahrheitstabelle ist $f = [0 \space \space 1]$. Jetzt habe ich aus der Zeitung von Terry Ritter gelesen, dass

Nichtlinearität ist die Anzahl der Bits, die sich in der Wahrheitstabelle einer Booleschen Funktion ändern müssen, um die nächste affine Funktion zu erreichen.

Dies bedeutet, dass der Nichtlinearitätswert eine ganze Zahl sein sollte.

Der Algorithmus zur Berechnung der Nichtlinearität besteht darin, zuerst die schnelle Walsh-Transformation zu verwenden, um das Walsh-Spektrum zu finden, und dann die Formel zu verwenden

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

wobei das Walsh-Spektrum berechnet wird, indem die Wahrheitstabelle der Funktion mit der entsprechenden Hadamard-Matrix multipliziert wird.

Also seit $k = 1$verwenden wir die Hadamard-Größenmatrix $2^1$ Geben des folgenden Walsh-Spektrums:

$$ \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 $$

Deshalb

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

Was vermisse ich?

---

Falls die Links tot sind, lauten die verlinkten Papiere:

1. Berechnung der Nichtlinearität boolescher Funktionen mit der Walsh-Hadamard-Transformation von Pedro Miguel Sosa
2. Messung der Nichtlinearität der Booleschen Funktion durch Walsh-Transformation von Terry Ritter

Answer 1

In dieser Formulierung müssen Sie den Ausgabebereich Ihrer Funktion in konvertieren $\{-1,+1\}$ über $$f`(x)=(-1)^{f(x)}$$ und wende den Walsh Hadamard auf die neue Funktion an $f`(x)$. Die Verwendung der Null-Eins-Formulierung bedeutet, dass Sie abhängig von der Anzahl der Variablen seitdem um eine Konstante versetzt sind

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

Siehe meine Antwort unten zu Booleschen Funktionen und Krypto. Sie kann angesichts Ihrer jüngsten Fragen hilfreich sein.

Wie werden boolesche Funktionen in der Kryptographie verwendet?

Answer 2

Zusätzlich zur Antwort von Kodlu konnte ich es herausfinden, nachdem ich die Zeitungen sorgfältig durchgelesen hatte. Wichtige Dinge zu beachten:

1. Wenn wir die Fast Walsh-Transformation für Boolesche Funktionen verwenden, die aus bestehen $\{0,1\}$ dann lautet die Formel für Nichtlinearität

... die Hälfte der Anzahl der Bits in der Funktion, abzüglich des Absolutwerts der unerwarteten Entfernung.

Das ist $$ 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)| $$

Daher haben wir für die Frage im ursprünglichen Beitrag

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

Alternativ schlägt Seite 20 hier ( alter Link ) vor, wie folgt vorzugehen: Nachdem Sie die Fast Walsh-Transformation gefunden haben,

1. Hinzufügen $2^{k-1}$zu jedem Eintrag in der Zeile mit Ausnahme des ersten Eintrags. Dies gibt uns eine neue Zeile, nennen Sie es$FHT'$

2. Wenn ein Eintrag in weniger als $2^{k-1}$es bleibt unverändert. Ansonsten, wenn ein Eintrag von$FHT'$ ist größer als $2^{k-1}$ dann subtrahieren Sie es von $2^k$.

3. Schließlich ist die Nichtlinearität das kleinste dieser angepassten Elemente.

2. Wenn wir die Fast Walsh-Transformation für Boolesche Funktionen verwenden, die aus bestehen $\{1,-1\}$ dann lautet die Formel für Nichtlinearität

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

weil

Mit realen Werten $\{1,-1\}$ verdoppelt die Größe und ändert das Vorzeichen der FWT-Ergebnisse

Quelle