Dlaczego nieliniowość tej funkcji boolowskiej jest obliczana do $\frac12$?
Używam metody przedstawionej w tym artykule, aby znaleźć nieliniowość funkcji
$$ f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \\ f(x) = x$$
Tabela prawdy jest $f = [0 \space \space 1]$. Teraz czytam z papieru Terry'ego Ritter tym
Nieliniowość to liczba bitów, które muszą ulec zmianie w tablicy prawdy funkcji boolowskiej, aby osiągnąć najbliższą funkcję afiniczną.
Oznacza to, że wartość nieliniowości powinna być liczbą całkowitą.
Algorytm obliczania nieliniowości polega najpierw na użyciu szybkiej transformaty Walsha w celu znalezienia widma Walsha, a następnie użyciu wzoru
$$Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$
gdzie widmo Walsha jest obliczane przez pomnożenie tablicy prawdy funkcji przez odpowiednią macierz Hadamarda.
Tak więc od $k = 1$używamy macierzy rozmiaru Hadamarda $2^1$ dając następujące widmo Walsha:
$$ \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 $$
W związku z tym
$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12$$
czego mi brakuje?
Jeśli linki są martwe, powiązane dokumenty to:
- Obliczanie nieliniowości funkcji boolowskich za pomocą transformacji Walsha-Hadamarda autorstwa Pedro Miguela Sosy
- Pomiar nieliniowości funkcji boolowskiej według transformacji Walsha według Terry'ego Rittera
Odpowiedzi
W tym sformułowaniu musisz przekonwertować zakres wyjściowy funkcji na $\{-1,+1\}$ przez $$f`(x)=(-1)^{f(x)}$$ i zastosuj Walsh Hadamard do nowej funkcji $f`(x)$. Użycie wyrażenia zero jeden oznacza, że jesteś wyłączony o stałą zależną od liczby zmiennych od tego czasu
$$ (-1)^u=1-2u $$ dla $u\in \{0,1\}.$
Zobacz moją odpowiedź poniżej na temat funkcji boolowskich i kryptowalut, może być przydatna, biorąc pod uwagę twoje ostatnie pytania.
W jaki sposób funkcje boolowskie są używane w kryptografii?
Oprócz odpowiedzi przez kodlu, po uważnym ponownym przeczytaniu artykułów, udało mi się to rozgryźć. Najważniejsze kwestie do zapamiętania:
1. Jeśli użyjemy szybkiej transformaty Walsha na funkcjach boolowskich składających się z $\{0,1\}$ to wzór na nieliniowość jest następujący
... połowa liczby bitów w funkcji, pomniejszona o wartość bezwzględną nieoczekiwanej odległości.
To jest $$ 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)| $$
Dlatego do pytania w oryginalnym poście mamy
$$Nl(f) = 2^{0} - |1| = 0$$
Alternatywnie, strona 20 tutaj ( link alt ) sugeruje, aby postępować w następujący sposób: Po znalezieniu transformacji Fast Walsh,
Dodaj $2^{k-1}$do każdego wpisu w wierszu z wyjątkiem pierwszego wpisu. To daje nam nowy wiersz, nazwij to$FHT'$
Jeśli wpis za mniej niż $2^{k-1}$pozostaje niezmieniony. W przeciwnym razie, jeśli wpis$FHT'$ jest większy niż $2^{k-1}$ następnie odejmij ją od $2^k$.
Wreszcie nieliniowość jest najmniejszym z tych dopasowanych elementów.
2. Jeśli użyjemy szybkiej transformaty Walsha na funkcjach boolowskich składających się z $\{1,-1\}$ to wzór na nieliniowość jest następujący
$$ Nl(f) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$
Dlatego
Używanie prawdziwych wartości $\{1,-1\}$ podwaja wielkość i zmienia znak wyników FWT
Źródło