1.6. Nonlinearity của hàm boolean

1.6.1. Biến đổi Fourier

Với mỗi vector \(\bm{a} = (a_1, \ldots, a_n) \in \mathbb{F}_2^n\), ta kí hiệu \(\langle \bm{a}, \bm{x} \rangle\) là hàm sau:

(1.7)\[\langle \bm{a}, \bm{x} \rangle = a_1 x_1 \oplus a_2 x_2 \oplus \ldots \oplus a_n x_n.\]

Mỗi hàm boolean \(f(\bm{x}) = f(x_1, x_2, \ldots, x_n)\) sẽ được biểu diễn dưới dạng duy nhất với

(1.8)\[f(\bm{x}) = 2^{-n} \sum_{\bm{a} \in \mathbb{F}_2^n} F_f (\bm{a}) \cdot (-1)^{\langle \bm{a}, \bm{x} \rangle},\]

trong đó

(1.9)\[F_f (\bm{a}) = \sum_{\bm{x} \in \mathbb{F}_2^n} f(\bm{x}) \cdot (-1)^{\langle \bm{a}, \bm{x} \rangle}.\]

Khi đó, tập hợp \(\{F_f (\bm{a}), \bm{a} \in \mathbb{F}_2^n \}\) được gọi là phổ Fourier (hay spectre Fourier) của hàm boolean \(f\).

Chú ý 1.22

Đầu tiên ta có nhận xét rằng, với vector \(\bm{z}\) cố định thì

(1.10)\[\begin{split}\sum_{\bm{a} \in \mathbb{F}_2^n} (-1)^{\langle \bm{a}, \bm{z} \rangle} = \begin{cases} 0, \quad & \text{nếu } \bm{z} \neq \bm{0} \\ 2^n, \quad & \text{nếu } \bm{z} = \bm{0}. \end{cases}\end{split}\]

Chứng minh

Để chứng minh nhận xét này, ta thấy rằng nếu \(\bm{z} \neq \bm{0}\) thì có ít nhất một bit \(z_i \neq 0\).

Ta chọn vector

\[\Delta = (0, \ldots, 0, 1, 0, \ldots, 0)\]

với bit \(1\) nằm ở vị trí \(i\).

Khi đó với mọi vector \(\bm{a} \in \mathbb{F}_2^n\) tồn tại duy nhất vector \(\bm{a}' \in \mathbb{F}_2^n\) sao cho \(\bm{a} \oplus \bm{a}' = \Delta\).

Ta suy ra \(\langle \bm{a} \oplus \bm{a}', \bm{z} \rangle = \langle \Delta, \bm{z} \rangle = 1\) vì \(z_i \cdot 1 = 1\), các vị trí còn lại \(z_j \cdot 0 = 0\).

Lý do ta chọn vector \(\Delta\) như vậy là vì

\[\langle \bm{a} \oplus \bm{a}', \bm{z} \rangle = \langle \bm{a}, \bm{z} \rangle \oplus \langle \bm{a}', \bm{z} \rangle = 1,\]

tương đương với \(\langle \bm{a}, \bm{z} \rangle = 1 \oplus \langle \bm{a}', \bm{z} \rangle\).

Do đó \(\langle \bm{a}, \bm{z} \rangle\) và \(\langle \bm{a}', \bm{z} \rangle\) là hai bit khác nhau, dẫn tới \((-1)^{\langle \bm{a}, \bm{z} \rangle}\) và \((-1)^{\langle \bm{a}', \bm{z} \rangle}\) là hai số trái dấu nhau nên tổng chúng là \(0\). Chúng ta có \(2^n / 2\) cặp như vậy và tổng cuối cùng là \(0\).

Trong trường hợp \(\bm{z} = \bm{0}\) thì \(\langle \bm{a}, \bm{z} \rangle = \bm{0}\) với mọi \(\bm{a} \in \mathbb{F}_2^n\). Do đó \((-1)^{\langle \bm{a}, \bm{z} \rangle} = (-1)^0 = 1\) với mọi vector \(\bm{a}\). Hàm boolean \(n\) biến có \(2^n\) vector \(\bm{a}\) nên tổng là \(2^n \cdot 1 = 2^n\).

Đẳng thức (1.10) đã được chứng minh. Ta quay lại bài toán.

Chứng minh

Với mọi vector \(\bm{x} \in \mathbb{F}_2^n\), ta khai triển từ vế phải của (1.8) và từ (1.9):

\[\begin{split}& 2^{-n} \sum_{\bm{a} \in \mathbb{F}_2^n} F_f (\bm{a}) \cdot (-1)^{\langle \bm{a}, \bm{x} \rangle} \\ = & 2^{-n} \sum_{\bm{a} \in \mathbb{F}_2^n} \left( \sum_{\bm{y} \in \mathbb{F}_2^n} f(\bm{y}) \cdot (-1)^{\langle \bm{a}, \bm{y} \rangle} \right) \cdot (-1)^{\langle \bm{a}, \bm{x} \rangle} \\ = & 2^{-n} \sum_{\bm{y} \in \mathbb{F}_2^n} f(\bm{y}) \sum_{\bm{a} \in \mathbb{F}_2^n} (-1)^{\langle \bm{a}, \bm{y} \oplus \bm{x} \rangle}.\end{split}\]

Theo (1.10), nếu ta coi \(\bm{y} \oplus \bm{x} = \bm{z}\) thì

\[\begin{split}\sum_{\bm{a} \in \mathbb{F}_2^n} (-1)^{\langle \bm{a}, \bm{y} \oplus \bm{x} \rangle} = \begin{cases} 0, \quad & \text{nếu } \bm{y} \oplus \bm{x} \neq \bm{0} \\ 2^n, \quad & \text{nếu } \bm{y} \oplus \bm{x} = \bm{0}, \end{cases}\end{split}\]

nghĩa là trong tổng trên thì chỉ có \(\bm{y}\) thỏa \(\bm{y} \oplus \bm{x} = \bm{0}\) thì \(f(\bm{y})\) không bị triệt tiêu. Nói cách khác là \(\bm{y} = \bm{x}\) và do đó tổng trên còn lại \(2^{-n} (f(\bm{x}) \cdot 2^n) = f(\bm{x})\) và ta có điều phải chứng minh.

Ví dụ 1.47

Xét hàm boolean \(f(x_1, x_2) = (1, 0, 0, 1)\).

Xét \(\bm{a} = (0, 0)\). Ta có:

Với \(\bm{x} = (0, 0)\),

\[f(\bm{x}) = 1, \ \langle \bm{a}, \bm{x} \rangle = 0 \cdot 0 + 0 \cdot 0 = 0.\]

Với \(\bm{x} = (0, 1)\),

\[f(\bm{x}) = 0, \langle \bm{a}, \bm{x} \rangle = 0 \cdot 0 + 0 \cdot 1 = 0.\]

Với \(\bm{x} = (1, 0)\),

\[f(\bm{x}) = 0, \langle \bm{a}, \bm{x} \rangle = 0 \cdot 1 + 0 \cdot 0 = 0.\]

Với \(\bm{x} = (1, 1)\),

\[f(\bm{x}) = 1, \langle \bm{a}, \bm{x} \rangle = 0 \cdot 1 + 0 \cdot 1 = 0.\]

Ta suy ra

\[F_f (\bm{a}) = 1 \cdot (-1)^0 + 0 \cdot (-1)^0 + 0 \cdot (-1)^0 + 1 \cdot (-1)^0 = 2\]

khi \(\bm{a} = (0, 0)\).

Tương tự, ta có các giá trị \(F_f (\bm{a})\) sau:

• với \(\bm{a} = (0, 1)\), \(F_f (\bm{a}) = F_f (0, 1) = 0\);

• với \(\bm{a} = (1, 0)\), \(F_f (\bm{a}) = F_f (1, 0) = 0\);

• với \(\bm{a} = (1, 1)\), \(F_f (\bm{a}) = F_f (1, 1) = 2\).

Bây giờ ta đã có đủ \(F_f(\bm{a})\) với \(\bm{a} \in \mathbb{F}_2^2\) nên ta có thể kiểm chứng với mọi \(\bm{x} \in \mathbb{F}_2^2\) thỏa công thức (1.8).

1.6.2. Biến đổi Walsh-Hadamard

Với mỗi hàm boolean \(f(x_1, x_2, \ldots, x_n) = f(\bm{x})\) ta định nghĩa một hàm tương ứng như sau:

\[f^*(\bm{x}) = (-1)^{f(\bm{x})}.\]

Ta định nghĩa \(\langle \bm{a}, \bm{x} \rangle\) như trên.

Khi đó hàm \(f^*(\bm{x})\) sẽ có dạng

(1.11)\[f^*(\bm{x}) = 2^{-n} \sum_{\bm{a} \in \mathbb{F}_2^n} W_f (\bm{a}) (-1)^{\langle \bm{a}, \bm{x} \rangle},\]

trong đó

(1.12)\[W_f (\bm{a}) = \sum_{\bm{x} \in \mathbb{F}_2^n} (-1)^{f(\bm{x}) \oplus \langle \bm{a}, \bm{x} \rangle}.\]

Tập hợp \(\{ W_f (\bm{a}), \bm{a} \in \mathbb{F}_2^n \}\) được gọi là phổ Walsh (hay spectre Walsh) của hàm \(f(\bm{x})\).

Các giá trị \(W_f (\bm{a})\) được gọi là hệ số Walsh.

Chứng minh

Tương tự như trên, ta khai triển vế phải của (1.11) và thay (1.12) vào

\[\begin{split}& 2^{-n} \sum_{\bm{a} \in \mathbb{F}_2^n} W_f (\bm{a}) (-1)^{\langle \bm{a}, \bm{x} \rangle} \\ = & 2^{-n} \sum_{\bm{a} \in \mathbb{F}_2^n} \left( \sum_{\bm{y} \in \mathbb{F}_2^n} (-1)^{f(\bm{y}) \oplus \langle \bm{a}, \bm{y} \rangle} \right) (-1)^{\langle \bm{a}, \bm{x} \rangle} \\ = & 2^{-n} \sum_{\bm{y} \in \mathbb{F}_2^n} (-1)^{f(\bm{y})} \sum_{\bm{a} \in \mathbb{F}_2^n} (-1)^{\langle \bm{a}, \bm{y} \oplus \bm{x} \rangle}.\end{split}\]

Cũng từ (1.10), tương tự như trên ta có

\[\begin{split}\sum_{\bm{a} \in \mathbb{F}_2^n} (-1)^{\langle \bm{a}, \bm{y} \oplus \bm{x} \rangle} = \begin{cases} 0, & \quad \text{nếu } \bm{y} \oplus \bm{x} \neq \bm{0} \\ 2^n, & \quad \text{nếu } \bm{y} \oplus \bm{x} = \bm{0}. \end{cases}\end{split}\]

Do đó trong các \(\bm{y} \in \mathbb{F}_2^n\) thì chỉ có \(\bm{y} = \bm{x}\) không bị triệt tiêu nên kết quả là

\[2^{-n} \cdot (-1)^{f(\bm{x})} \cdot 2^n = (-1)^{f(\bm{x})} = f^* (\bm{x}).\]

Các hệ số Walsh liên hệ với nhau bởi công thức

\[\begin{split}\sum_{\bm{a} \in \mathbb{F}_2^n} W_f (\bm{a}) W_f (\bm{a} \oplus \bm{d}) = \begin{cases} 2^{2n}, & \bm{d} = \bm{0} \\ 0, & \bm{d} \neq \bm{0}. \end{cases}\end{split}\]

Trường hợp \(\bm{d} = \bm{0}\) được gọi là đẳng thức Parcel:

\[\sum_{\bm{a} \in \mathbb{F}_2^n} (W_f (\bm{a}))^2 = 2^{2n}.\]

1.6.3. Tính chất của biến đổi Walsh-Hadamard

1. \(W_f(\bm{0}) = 2^n - 2 \mathrm{wt} (f)\), và \(W_f(\bm{0}) = 0\) khi và chỉ khi \(f\) là hàm cân bằng.

2. Nếu \(g = \bar{f}\) thì \(W_g(\bm{a}) = -W_f(\bm{a})\) với mọi \(\bm{a} \in \mathbb{F}_2^n\).

3. Nếu \(g(\bm{x}) = f(\bm{x} \oplus \bm{b})\) với vector \(\bm{b}\) nào đó, thì

\[\begin{split}W_g(\bm{a}) & = \sum_x (-1)^{f(\bm{x} \oplus \bm{b}) \oplus \langle \bm{a}, \bm{x} \rangle} \\ & = \sum_x (-1)^{f(\bm{x}) \oplus \langle \bm{a}, \bm{x} \oplus \bm{b} \rangle} \\ & = (-1)^{\langle \bm{a}, \bm{b} \rangle} W_f(\bm{a}).\end{split}\]

4. Đặt \(f \in \mathcal{F}_n\), \(\bm{b} \in \mathbb{F}_2^n\), \(g(\bm{x}) = f(\bm{x}) \oplus \langle \bm{b}, \bm{x} \rangle\). Khi đó

\[\begin{split}W_g(\bm{a}) & = \sum_x (-1)^{f(\bm{x}) \oplus \langle \bm{b}, \bm{x} \rangle \oplus \langle \bm{a}, \bm{x} \rangle} \\ & = \sum_x (-1)^{f(\bm{x}) \oplus \langle \bm{b} \oplus \bm{a}, \bm{x} \rangle} \\ & = W_f(\bm{b} \oplus \bm{a}).\end{split}\]

5. Đặt \(f(\bm{x}) = c\) là hằng số. Hàm \(c \oplus \langle \bm{a}, \bm{x} \rangle\) là hàm tuyến tính với mọi \(\bm{a} \neq \bm{0}\). Hệ quả là \(W_f(\bm{a}) = 0\) với mọi vector \(\bm{a}\) khác không, trừ khi

\[\begin{split} W_f(\bm{0}) = 2^n - 2 \mathrm{wt} (f) = \begin{cases} - 2^n, & \, \text{nếu} \, c = 1, \\ \quad 2^n, & \, \text{nếu} \, c = 0. \end{cases}\end{split}\]

6. Đặt \(f(\bm{x}) = c \oplus \langle \bm{b}, \bm{x} \rangle\) là hàm affine. Khi đó, theo tính chất 4 và 5 suy ra \(W_f(\bm{a}) = 0\) với mọi \(\bm{a} \neq \bm{0}\), và \(W_f(\bm{b}) = (-1)^c \cdot 2^n\).

7. Đặt \(f(\bm{x}, \bm{y}) = g(\bm{x}) \oplus h(\bm{y})\) với \(g \in \mathcal{F}_n\) và \(h \in \mathcal{F}_m\) và hai tập hợp biến \(\bm{x}\) và \(\bm{y}\) không giao nhau. Nói cách khác \(f\) là hàm boolean \(n+m\) biến. Khi đó với mọi \(\bm{a} \in \mathbb{F}_2^n\) và \(\bm{b} \in \mathbb{F}_2^n\) thì

\[\begin{split}W_f(\bm{a} \bm{b}) & = \sum_{\bm{x}, \bm{y}} (-1)^{g(\bm{x}) \oplus h(\bm{y}) \oplus \langle \bm{a}, \bm{x} \rangle \oplus \langle \bm{b}, \bm{y} \rangle} \\ & = \sum_{\bm{x}} (-1)^{g(\bm{x}) \oplus \langle \bm{a}, \bm{x} \rangle} \sum_{\bm{y}} (-1)^{h(\bm{y}) \oplus \langle \bm{b}, \bm{y} \rangle} \\ & = W_g(\bm{a}) \cdot W_h(\bm{b}).\end{split}\]

8. Đặt \(f(x_1, \ldots, x_n)\) giả phụ thuộc vào biến \(x_i\). Khi đó \(W_f(\bm{a}) = 0\) với mọi vector \(\bm{a}\) mà \(a_i = 1\).

Nói cách khác, nếu đặt \(\bm{x}' = (x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n)\) và \(\bm{a}' = (a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n)\) và để ý rằng \(\langle \bm{a}, \bm{x} \rangle = \langle \bm{a}', \bm{x}' \rangle \oplus a_i x_i\). Khi đó nếu \(a_i = 1\) thì

\[\begin{split}W_f(\bm{a}) & = \sum_{\bm{x}} (-1)^{f(\bm{x}) \oplus \langle \bm{a}, \bm{x} \rangle} \\ & = \sum_{\substack{\bm{x}, \\ x_i = 0}} (-1)^{f(\bm{x}) \oplus \langle \bm{a}', \bm{x}' \rangle} + \sum_{\substack{\bm{x}, \\ x_i = 1}} (-1)^{f(\bm{x}) \oplus \langle \bm{a}', \bm{x}' \rangle \oplus 1} = 0.\end{split}\]

Nếu \(f\) và \(g\) là hai hàm Boolean tương đương affine thì tập hợp giá trị tuyệt đối của tất cả phổ Hadamard của hai hàm trùng nhau.

Chứng minh

Đặt \(f^*(\bm{x}) = (-1)^{f(\bm{x})}\) thì

\[f^*(\bm{x}) = 2^{-n} \sum_{\bm{a} \in \FF_2^n} W_f(a) \cdot (-1)^{\langle \bm{a}, \bm{x} \rangle},\]

trong đó \(W_f(\bm{a}) = \sum\limits_{\bm{x} \in \FF_2^n} (-1)^{f(\bm{x}) \oplus \langle \bm{a}, \bm{x} \rangle}\).

Giả sử \(g(\bm{x}) = f(\bm{A} \bm{x} + \bm{b})\) với \(\bm{A}\) là ma trận khả nghịch \(n \times n\) trên \(\FF_2\) và \(\bm{b} \in \FF_2^n\).

Đặt \(\bm{y} = \bm{A} \bm{x} \oplus \bm{b}\) thì \(\bm{x} = \bm{A}^{-1}(\bm{y} \oplus \bm{b})\).

Đặt \(g^*(\bm{x}) = (-1)^{g(\bm{x})}\) thì

\[g^*(\bm{x}) = 2^{-n} \sum_{\bm{a} \in \FF_2^n} W_g(\bm{a}) \cdot (-1)^{\langle \bm{a}, \bm{x} \rangle},\]

trong đó

\[\begin{split}W_g(\bm{a}) & = \sum_{\bm{x} \in \FF_2^n} (-1)^{g(\bm{x}) \oplus \langle \bm{a}, \bm{x} \rangle} \\ & = \sum_{\bm{x} \in \FF_2^n} (-1)^{f(\bm{A} \bm{x} + \bm{b}) \oplus \langle \bm{a}, \bm{A}^{-1}(\bm{y} \oplus \bm{b}) \rangle} \\ & = \sum_{\bm{x} \in \FF_2^n} (-1)^{f(\bm{y}) \oplus \langle \bm{a}, \bm{A}^{-1} \bm{y} \rangle \oplus \langle \bm{a}, \bm{A}^{-1} \bm{b} \rangle} \\ & = (-1)^{\langle \bm{a}, \bm{A}^{-1} \bm{b} \rangle} \sum_{\bm{y} \in \FF_2^n} (-1)^{f(\bm{y}) \oplus \langle \bm{a}, \bm{A}^{-1} \bm{y} \rangle} \\ & = (-1)^{\langle \bm{a}, \bm{A}^{-1} \bm{b} \rangle} \sum_{\bm{y} \in \FF_2^n} (-1)^{f(\bm{y}) \oplus \langle \bm{A}^{-\top} \bm{a}, \bm{y} \rangle} \\ & = (-1)^{\langle \bm{a}, \bm{A}^{-1} \bm{b} \rangle} W_f(\bm{A}^{-\top} \bm{a}).\end{split}\]

Như vậy \(\lvert W_g(\bm{a}) \rvert = \lvert W_f(\bm{A}^{-\top} \bm{a}) \rvert\) nên ta có điều phải chứng minh.

1.6.4. Liên hệ giữa hệ số Fourier và hệ số Walsh

Chú ý 1.23

Quan hệ giữa hệ số Fourier và hệ số Walsh là biểu thức sau

\[W_f (\bm{a}) = 2^n \Delta (\bm{a}) - 2 F_f (\bm{a})\]

với

\[\begin{split}\Delta (\bm{a}) = \begin{cases} 1, \quad \text{nếu } \bm{a} = \bm{0} \\ 0, \quad \text{nếu } \bm{a} \neq \bm{0}. \end{cases}\end{split}\]

Chứng minh

Ta có

\[\begin{split}W_f (\bm{a}) + 2 F_f (\bm{a}) = & \sum_{\bm{x} \in \mathbb{F}_2^n} (-1)^{f(\bm{x}) \oplus \langle \bm{a}, \bm{x} \rangle} + 2 \sum_{\bm{x} \in \mathbb{F}_2^n} f(\bm{x}) (-1)^{\langle \bm{a}, \bm{x} \rangle} \\ = & \sum_{\bm{x} \in \mathbb{F}_2^n} (-1)^{\langle \bm{a}, \bm{x} \rangle} [(-1)^{f(\bm{x})} + 2 f(\bm{x})].\end{split}\]

Để ý rằng, nếu \(f(\bm{x}) = 0\) thì

\[(-1)^{f(\bm{x})} + 2 f(\bm{x}) = (-1)^0 + 2 \cdot 0 = 1,\]

còn nếu \(f(\bm{x}) = 1\) thì

\[(-1)^{f(\bm{x})} + 2 f(\bm{x}) = (-1)^1 + 2 \cdot 1 = 1.\]

Nói cách khác biểu thức trên trở thành

\[W_f (\bm{a}) + 2 F_f (\bm{a}) = \sum_{\bm{x} \in \mathbb{F}_2^n} (-1)^{\langle \bm{a}, \bm{x} \rangle}.\]

Từ (1.8) ta có

\[\begin{split}\sum_{\bm{x} \in \mathbb{F}_2^n} (-1)^{\langle \bm{a}, \bm{x} \rangle} = \begin{cases} 0, \quad &\text{nếu } \bm{a} \neq \bm{0} \\ 2^n, \quad & \text{nếu } \bm{a} = \bm{0}. \end{cases}\end{split}\]

Như vậy nếu đặt \(\Delta(\bm{a}) = \begin{cases} 1, \text{nếu } \bm{a} = \bm{0} \\ 0, \text{nếu } \bm{a} \neq \bm{0} \end{cases}\) thì ta có điều phải chứng minh.

Chú ý 1.24

Khi \(\bm{a} = \bm{0}\) thì với mọi \(\bm{x} \in \mathbb{F}_2^n\) ta đều có \(\langle \bm{a}, \bm{x} \rangle = 0\). Do đó

\[F_f (\bm{0}) = \sum_{\bm{x} \in \mathbb{F}_2^n} f(\bm{x}) (-1)^{\langle \bm{a}, \bm{x} \rangle} = \sum_{\bm{x} \in \mathbb{F}_2^n} f(\bm{x}) (-1)^0 = \mathrm{wt}(f),\]

suy ra

(1.13)\[W_f (\bm{0}) = 2^n - 2 wt(f) \Leftrightarrow wt(f) = 2^{n-1} - \frac{1}{2} W_f (\bm{0}).\]

1.6.5. Hàm Bent

Ta kí hiệu \(\mathcal{A}\) là tập hợp tất cả các hàm boolean affine với \(n\) biến, nghĩa là

\[\mathcal{A} = \{ a_0 \oplus a_1 x_1 \oplus \cdots \oplus a_n x_n \, | \, a_0, a_1, \ldots, a_n \in \mathbb{F}_2 \}.\]

Định nghĩa 1.75 (Nonlinearity của hàm boolean)

Nonlinearity của hàm boolean \(f\) bất kì được định nghĩa là khoảng cách Hamming từ \(f\) tới \(\mathcal{A}\), hay nói cách khác \(N_f = d(f, \mathcal{A})\).

Chú ý 1.25

Xét hàm \(f\) với \(n\) biến và phổ Walsh tương ứng của hàm \(f\) là \(\{ W_f (\bm{a}), \bm{a} \in \mathbb{F}_2^n \}\). Khi đó

(1.14)\[N_f = 2^{n-1} - \frac{1}{2} \max_{\bm{a} \in \mathbb{F}_2^n} \lvert W_f (\bm{a}) \rvert.\]

Chú ý 1.26

Từ đẳng thức Parcel ta có

\[\begin{split}& 2^n \cdot \left(\max_{\bm{a} \in \mathbb{F}_2^n} (W_f (\bm{a}))^2\right) \geqslant \sum_{\bm{a} \in \mathbb{F}_2^n} (W_f (\bm{a}))^2 = 2^{2n} \\ \Leftrightarrow & \max_{\bm{a} \in \mathbb{F}_2^n} (W_f (\bm{a}))^2 \geqslant \frac{2^{2n}}{2^n} = 2^n \\ \Leftrightarrow & \max_{\bm{a} \in \mathbb{F}_2^n} \lvert W_f (\bm{a}) \rvert \geqslant 2^{n/2}.\end{split}\]

Từ nhận xét trên và từ định nghĩa nonlinearity ở trên ta có

\[N_f \leqslant 2^{n-1} - \frac{1}{2} 2^{n / 2}.\]

Hàm \(f\) khiến dấu bằng xảy ra được gọi là hàm Bent. Điều kiện cần và đủ để tồn tại hàm Bent \(f\) có \(n\) biến là khi \(n = 2k\), tức là \(n\) chẵn.

Tính chất quan trọng của hàm Bent là với mọi vector \(\bm{a}\) thì

\[W_f (\bm{a}) = \pm 2^{n/2}.\]

Ví dụ 1.48

Với \(n = 2\), hàm \(f(x_1, x_2) = x_1 \oplus x_1 x_2\) là hàm Bent.

Ta có thể tính toán và thấy rằng \(W_f (0, 0) = 2\), \(W_f (0, 1) = -2\), \(W_f (1, 0) = 2\) và \(W_f (1, 1) = 2\).