Mengapa nonlinier dari fungsi Boolean ini mengevaluasi $\frac12$?

Question

Saya menggunakan metode yang disajikan dalam makalah untuk menemukan non-linear dari fungsi

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

Tabel kebenarannya adalah $f = [0 \space \space 1]$. Sekarang, saya membaca dari koran oleh Terry Ritter itu

Nonlinier adalah jumlah bit yang harus diubah dalam tabel kebenaran dari suatu fungsi Boolean untuk mencapai fungsi affine terdekat.

Ini berarti nilai nonlinier harus berupa bilangan bulat.

Algoritma untuk menghitung nonlinier adalah menggunakan Fast Walsh Transform untuk mencari spektrum Walsh, kemudian menggunakan rumus

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

dimana spektrum Walsh dihitung dengan mengalikan tabel kebenaran fungsinya dengan matriks Hadamard yang sesuai.

Jadi, sejak itu $k = 1$, kami menggunakan matriks ukuran Hadamard $2^1$ memberikan spektrum Walsh berikut:

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

Karena itu

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

Apa yang saya lewatkan?

---

Jika tautannya mati, makalah yang ditautkan adalah:

1. Menghitung Nonlinier dari Fungsi Boolean dengan Transformasi Walsh-Hadamard oleh Pedro Miguel Sosa
2. Mengukur Nonlinier Fungsi Boolean dengan Transformasi Walsh oleh Terry Ritter

Answer 1

Dalam formulasi ini, Anda perlu mengubah rentang keluaran fungsi menjadi $\{-1,+1\}$ melalui $$f`(x)=(-1)^{f(x)}$$ dan menerapkan Walsh Hadamard ke fungsi baru $f`(x)$. Menggunakan rumus nol satu berarti Anda melenceng dengan konstanta tergantung pada jumlah variabel sejak

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

Lihat jawaban saya di bawah ini tentang fungsi Boolean dan crypto, semoga bermanfaat mengingat pertanyaan terbaru Anda.

Bagaimana fungsi boolean digunakan dalam kriptografi?

Answer 2

Selain jawaban kodlu, setelah membaca ulang makalah dengan cermat, saya bisa mengetahuinya. Hal-hal penting yang perlu diperhatikan:

1. Jika kita menggunakan Fast Walsh Transform pada fungsi Boolean yang terdiri dari $\{0,1\}$ maka rumus untuk nonlinier adalah

... setengah jumlah bit dalam fungsi tersebut, dikurangi nilai absolut dari jarak yang tidak terduga.

Itu adalah $$ 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)| $$

Oleh karena itu, untuk pertanyaan di postingan asli yang kami miliki

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

Atau, halaman 20 di sini ( tautan alt ) menyarankan untuk melanjutkan sebagai berikut: Setelah menemukan transformasi Fast Walsh,

1. Menambahkan $2^{k-1}$ke setiap entri di baris kecuali entri pertama. Ini memberi kita baris baru, sebut saja$FHT'$

2. Jika entri kurang dari $2^{k-1}$itu tetap tidak berubah. Sebaliknya, jika entri$FHT'$ lebih besar dari $2^{k-1}$ lalu kurangi dari $2^k$.

3. Akhirnya, nonlinier adalah yang terkecil dari elemen yang disesuaikan ini.

2. Jika kita menggunakan Fast Walsh Transform pada fungsi Boolean yang terdiri dari $\{1,-1\}$ maka rumus untuk nonlinier adalah

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

Karena

Menggunakan nilai nyata $\{1,-1\}$ menggandakan besarnya dan mengubah tanda hasil FWT

Sumber