このブール関数の非線形性が次のように評価されるのはなぜですか $\frac12$？

Question

関数の非線形性を見つけるために、この論文で提示された方法を使用しています

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

真理値表は $f = [0 \space \space 1]$。今、私はから読んテリーリッターの論文こと

非線形性は、最も近いアフィン関数に到達するためにブール関数の真理値表で変更する必要があるビット数です。

これは、非線形性の値が整数でなければならないことを意味します。

非線形性を計算するアルゴリズムは、最初に高速ウォルシュ変換を使用してウォルシュスペクトルを見つけ、次に次の式を使用することです。

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

ここで、ウォルシュスペクトルは、関数の真理値表に対応するアダマール行列を乗算することによって計算されます。

だから、 $k = 1$、サイズのアダマール行列を使用します $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$$

何が足りないのですか？

---

リンクが切れている場合、リンクされている論文は次のとおりです。

1. Pedro MiguelSosaによるWalsh-Hadamard変換を使用したブール関数の非線形性の計算
2. ウォルシュ変換によってブール関数の非直線性を測定テリーリッターで

Answer 1

この定式化では、関数の出力範囲を次のように変換する必要があります。 $\{-1,+1\}$ 経由 $$f`(x)=(-1)^{f(x)}$$ ウォルシュアダマールを新しい関数に適用します $f`(x)$。ゼロワンの定式化を使用すると、変数の数に応じて定数がずれることを意味します。

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

ブール関数と暗号については、以下の私の回答を参照してください。最近の質問を考えると役立つ場合があります。

ブール関数は暗号化でどのように使用されますか？

Answer 2

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ページ（代替リンク）は、次のように進めることを提案しています。FastWalsh変換を見つけた後、

1. 追加 $2^{k-1}$最初のエントリを除く行の各エントリに。これは私たちに新しい行を与えます、それを呼んでください$FHT'$

2. 未満のエントリの場合 $2^{k-1}$変更はありません。それ以外の場合、$FHT'$ より大きい $2^{k-1}$ 次にそれを $2^k$。

3. 最後に、非線形性はこれらの調整された要素の中で最小です。

2.で構成されるブール関数で高速ウォルシュ変換を使用する場合 $\{1,-1\}$ すると、非線形性の式は次のようになります。

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

なぜなら

実数値の使用 $\{1,-1\}$ 大きさを2倍にし、FWT結果の符号を変更します

ソース