Dlaczego nieliniowość tej funkcji boolowskiej jest obliczana do $\frac12$?

Dec 17 2020

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:

  1. Obliczanie nieliniowości funkcji boolowskich za pomocą transformacji Walsha-Hadamarda autorstwa Pedro Miguela Sosy
  2. Pomiar nieliniowości funkcji boolowskiej według transformacji Walsha według Terry'ego Rittera

Odpowiedzi

4 kodlu Dec 18 2020 at 05:12

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?

2 E.Nole Dec 19 2020 at 03:31

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,

  1. Dodaj $2^{k-1}$do każdego wpisu w wierszu z wyjątkiem pierwszego wpisu. To daje nam nowy wiersz, nazwij to$FHT'$

  2. 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$.

  3. 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