Bu Boole işlevinin doğrusal olmama durumu neden $\frac12$?

Question

Fonksiyonun doğrusal olmayışını bulmak için bu yazıda sunulan yöntemi kullanıyorum

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

Doğruluk tablosu $f = [0 \space \space 1]$. Şimdi, okunan Terry Ritter kağıt o

Doğrusal olmayanlık, en yakın afin işleve ulaşmak için bir Boole işlevinin doğruluk tablosunda değişmesi gereken bit sayısıdır.

Bu, doğrusal olmayan değerin bir tam sayı olması gerektiği anlamına gelir.

Doğrusal olmamayı hesaplamak için kullanılan algoritma, önce Walsh spektrumunu bulmak için Hızlı Walsh Dönüşümünü kullanmak, ardından formülü kullanmaktır.

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

Walsh spektrumu, fonksiyonun doğruluk tablosunun karşılık gelen Hadamard matrisi ile çarpılmasıyla hesaplanır.

O zamandan beri $k = 1$Hadamard boyut matrisini kullanıyoruz $2^1$ aşağıdaki Walsh spektrumunu verir:

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

Bu nedenle

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

Neyi kaçırıyorum?

---

Bağlantıların kesilmesi durumunda, bağlantılı belgeler şunlardır:

1. Boole Fonksiyonlarının Doğrusal Olmayanlığını Walsh-Hadamard Dönüşümü ile Hesaplama by Pedro Miguel Sosa
2. Boole Fonksiyonunun Doğrusal Olmayanlığını Ölçme, Walsh Dönüşümü , Terry Ritter

Answer 1

Bu formülasyonda, fonksiyonunuzun çıktı aralığını şu değere dönüştürmeniz gerekir: $\{-1,+1\}$ üzerinden $$f`(x)=(-1)^{f(x)}$$ ve Walsh Hadamard'ı yeni işleve uygulayın $f`(x)$. Sıfır bir formülasyonunu kullanmak, değişkenlerin sayısına bağlı olarak sabit kaldığınız anlamına gelir.

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

Boole fonksiyonları ve kripto ile ilgili aşağıdaki cevabıma bakın, son sorularınız göz önüne alındığında faydalı olabilir.

Kriptografide boole fonksiyonları nasıl kullanılır?

Answer 2

Kodlu'nun cevabına ek olarak, kağıtları tekrar dikkatlice okuduktan sonra çözebildim. Dikkat edilmesi gereken önemli şeyler:

1. Hızlı Walsh Dönüşümünü aşağıdakilerden oluşan Boole işlevlerinde kullanırsak $\{0,1\}$ daha sonra doğrusal olmama formülü

... fonksiyondaki bit sayısının yarısı, beklenmedik mesafenin mutlak değeri çıkarılır.

Yani $$ 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)| $$

Bu nedenle, orijinal gönderideki soru için elimizde

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

Alternatif olarak, sayfa 20 burada ( alt bağlantı ) aşağıdaki gibi ilerlemeyi önerir: Hızlı Walsh dönüşümünü bulduktan sonra,

1. Ekle $2^{k-1}$ilk giriş hariç satırdaki her girişe. Bu bize yeni bir sıra veriyor, ara onu$FHT'$

2. Daha az bir giriş varsa $2^{k-1}$değişmeden kalır. Aksi takdirde,$FHT'$ daha büyüktür $2^{k-1}$ sonra onu çıkarın $2^k$.

3. Son olarak, doğrusal olmama, bu ayarlanmış elemanların en küçüğüdür.

2. Hızlı Walsh Dönüşümünü aşağıdakilerden oluşan Boole fonksiyonları üzerinde kullanırsak $\{1,-1\}$ daha sonra doğrusal olmama formülü

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

Çünkü

Gerçek değerleri kullanmak $\{1,-1\}$ FWT sonuçlarının büyüklüğünü iki katına çıkarır ve işaretini değiştirir

Kaynak