為什麼這個布爾函式的非線性評估為1212frac12?
我正在使用本文介紹的方法來查找函式的非線性
$$ f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \ f(x) = x $$
真值表是 $ f = [0 \space \space 1] $ . 現在，我從Terry Ritter 的論文中讀到
非線性是布爾函式的真值表中必須改變以達到最接近的仿射函式的位數。
這意味著非線性值應該是一個整數。
計算非線性的算法是先用快速沃爾什變換求沃爾什譜，然後用公式
$$ Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$
其中 Walsh 譜是通過將函式的真值表乘以相應的 Hadamard 矩陣來計算的。
所以，既然 $ k = 1 $ ，我們使用大小的 Hadamard 矩陣 $ 2^1 $ 給出以下沃爾什譜：
$$ \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 $$
所以
$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12 $$
我錯過了什麼？
如果連結失效，連結的論文是：
- Pedro Miguel Sosa用 Walsh-Hadamard 變換計算布爾函式的非線性
- Terry Ritter通過沃爾什變換測量布爾函式非線性
在這個公式中，您需要將函式的輸出範圍轉換為 $ {-1,+1} $ 通過$$ f
(x)=(-1)^{f(x)} $$並將 Walsh Hadamard 應用於新功能 $ f(x) $ . 使用零一公式意味著你偏離了一個常數，這取決於變數的數量，因為$$ (-1)^u=1-2u $$ 為了 $ u\in {0,1}. $
請參閱下面關於布爾函式和加密的答案，考慮到您最近的問題，它可能很有用。
除了 kodlu 的回答之外，仔細翻閱論文後，我也能弄明白了。需要注意的關鍵事項：
1. 如果我們在布爾函式上使用快速沃爾什變換 $ {0,1} $ 那麼非線性的公式是
…函式中位數的一半，減去意外距離的絕對值。
那是 $$ 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)| $$
因此，對於原帖中的問題，我們有
$$ Nl(f) = 2^{0} - |1| = 0 $$
或者，此處的第 20 頁（替代連結）建議按以下方式進行：找到快速沃爾什變換後，
- 添加 $ 2^{k-1} $ 到除第一個條目之外的行中的每個條目。這給了我們一個新行，稱之為 $ FHT’ $
- 如果條目小於 $ 2^{k-1} $ 它保持不變。否則，如果一個條目 $ FHT’ $ 大於 $ 2^{k-1} $ 然後從中減去 $ 2^k $ .
- 最後，非線性是這些調整元素中最小的。
2. 如果我們在布爾函式上使用快速沃爾什變換，包括 $ {1,-1} $ 那麼非線性的公式是
$$ Nl(f) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$
因為
使用真實值 $ {1,-1} $ 將幅度加倍並改變 FWT 結果的符號