Симметричная криптография

Lời giải cho quyển sách [21] của Н.Н. Токарева.

Глава 3. Булевы функции. Комбинаторный подход

Câu 16

Chứng minh rằng, hàm Boolean \(f\) tuyến tính khi và chỉ khi \(f(\bm{x} \oplus \bm{y}) = f(\bm{x}) \oplus f(\bm{y})\) với mọi \(\bm{x}\), \(\bm{y}\). Tương tự kiểm tra hàm Boolean là affine khi và chỉ khi \(f(\bm{x} \oplus \bm{y}) = f(\bm{x}) \oplus f(\bm{y}) \oplus f(\bm{0})\).

Chứng minh cho hàm tuyến tính

Chiều thuận. Nếu \(f\) là hàm tuyến tính thì nó có dạng

\[f(x_1, \ldots, x_n) = a_n x_n \oplus \cdots \oplus a_1 x_1\]

nên ta tính \(f(\bm{x} \oplus \bm{y})\) như sau

\[\begin{split}f(\bm{x} \oplus \bm{y}) & = a_n (x_n \oplus y_n) \oplus \cdots \oplus a_1 (x_1 \oplus y_1) \\ & = (a_n x_n \oplus \cdots \oplus a_1 x_1) \oplus (a_n y_n \oplus \cdots \oplus a_1 y_1) \\ & = f(\bm{x}) \oplus f(\bm{y}).\end{split}\]

Chiều nghịch. Với \(f(\bm{x} \oplus \bm{y}) = f(\bm{x}) \oplus f(\bm{y})\), đặt dạng ANF của \(f\) là

\[f(x_1, \ldots, x_n) = \left(\bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} x_{i_1} \cdots x_{i_k}\right) \oplus a_0.\]

Khi đó

\[f(\bm{x} \oplus \bm{y}) = \left(\bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} (x_{i_1} \oplus y_{i_1}) \cdots (x_{i_k} \oplus y_{i_k})\right) \oplus a_0,\]

và

\[\begin{split}f(\bm{x}) \oplus f(\bm{y}) & = \left(\bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} x_{i_1} \cdots x_{i_k}\right) \oplus a_0 \oplus \left(\bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} y_{i_1} \cdots y_{i_k}.\right) \oplus a_0 \\ & = \bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} (x_{i_1} \cdots x_{i_k} \oplus y_{i_1} \cdots y_{i_k}).\end{split}\]

Như vậy, khi đồng nhất hệ số \(a_{i_1, \ldots, i_k}\) của \(f(\bm{x} \oplus \bm{y})\) và \(f(\bm{x}) \oplus f(\bm{y})\) thì ta có

\[(x_{i_1} \oplus y_{i_1}) \cdots (x_{i_k} \oplus y_{i_k}) = x_{i_1} \cdots x_{i_k} \oplus y_{i_1} \cdots y_{i_k}.\]

Ở vế trái khi khai triển ra ta sẽ nhận được các đơn thức dạng \(x_{i_1} y_{i_2} y_{i_3} \cdots y_{i_k}\) khi \(k > 1\), tuy nhiên ở vế phải chỉ có đúng hai đơn thức là \(x_{i_1} \cdots x_{i_k}\) và \(y_{i_1} \cdots y_{i_k}\). Do đó các hệ số \(a_{i_1, \ldots, i_k}\) với \(k > 1\) phải bằng \(0\). Hay nói cách khác bậc của ANF là \(1\). Ngoài ra \(f(\bm{x} \oplus \bm{y})\) có hệ số tự do \(a_0\) còn \(f(\bm{x}) \oplus f(\bm{y})\) thì không có nên khi đồng nhất hệ số cũng cho ta \(a_0 = 0\). Như vậy \(f\) là hàm tuyến tính.

Chứng minh cho hàm affine

Chiều thuận. Nếu \(f\) là hàm tuyến tính thì nó có dạng

\[f(x_1, \ldots, x_n) = a_n x_n \oplus \cdots \oplus a_1 x_1 \oplus a_0\]

và ta chứng minh tương tự cho trường hợp hàm tuyến tính với lưu ý \(f(\bm{0}) = a_0\).

Chiều nghịch. Chứng minh tương tự cho trường hợp hàm tuyến tính.

Câu 17

Tìm số đỉnh và số cạnh của đồ thị \(E^n\). Có bao nhiêu vector \(\bm{x}, \bm{y} \in E^n\) sao cho \(d(\bm{x}, \bm{y}) = k\)?

Mỗi đỉnh của \(E^n\) biểu diễn một vector dạng

\[(z_1, \ldots, z_n), \quad z_i \in \{ 0, 1 \}\]

nên \(E^n\) có \(2^n\) đỉnh. Mỗi đỉnh nối với \(n\) đỉnh khác (khác nhau chỉ ở vị trí \(z_i\)) nên \(\deg v_i = n\) với \(i = \overline{1, 2^n}\). Theo định lí cơ bản về số cạnh của đồ thị (Định lý 8) thì

\[\text{số cạnh} = \dfrac{1}{2} \sum_{i=1}^{2^n} \deg v_i = \dfrac{1}{2} \cdot n \cdot 2^n = n \cdot 2^{n-1}.\]

Để \(d(\bm{x}, \bm{y}) = k\) thì đầu tiên ta chọn \(k\) vị trí khác nhau với \(C_n^k\) cách. Với mỗi vị trí khác nhau ta có hai cách chọn \(x_i\) và \(y_i\) là

\[\begin{split}\begin{cases} x_i = 1 \\ y_i = 0 \end{cases}, \quad \text{hoặc} \ \begin{cases} x_i = 0 \\ y_i = 1 \end{cases}.\end{split}\]

Do đó có \(2^k\) cách chọn cho các vị trí khác nhau, còn \(n - k\) vị trí còn lại thì chọn tùy ý nên có \(2^{n-k}\) cách.

Đáp án là \(C_n^k \cdot 2^k \cdot 2^{n-k} = C_n^k \cdot 2^n\).

Câu 18

Tìm lực lượng của mặt cầu \(S_r(\bm{x}) = \{ \bm{y} : d(\bm{x}, \bm{y}) = r \}\) và hình cầu \(B_r(\bm{x}) = \{ \bm{y} : d(\bm{x}, \bm{y}) \leqslant r \}\).

Đối với mặt cầu thì đáp án chính là bài 17, nghĩa là \(\lvert S_r(\bm{x}) \rvert = 2^r \cdot C_n^r\).

Đối với hình cầu \(B_r(\bm{x})\) ta xét tất cả giá trị từ \(0\) tới \(r\):

• khi \(d(\bm{x}, \bm{y}) = 0\) thì có \(2^n \cdot C_n^0\) cách chọn;

• khi \(d(\bm{x}, \bm{y}) = 1\) thì có \(2^n \cdot C_n^1\) cách chọn;

• tương tự, khi \(d(\bm{x}, \bm{y}) = i\) thì có \(2^n \cdot C_n^i\) cách chọn;

• cho tới khi \(d(\bm{x}, \bm{y}) = r\) thì có \(2^n \cdot C_n^r\) cách chọn.

Như vậy lực lượng của hình cầu là tổng tất cả giá trị trên:

\[\lvert B_r(\bm{x}) \rvert = 2^n \cdot (C_n^0 + C_n^1 + \cdots + C_n^r).\]

Глава 5. Криптографические свойства булевых функций

[TODO] Câu 31

Chứng minh rằng khoảng cách từ hàm Boolean \(f\) với \(n\) biến tới hàm Boolean affine

\[l_{\bm{a}, b}(\bm{x}) = a_1 x_1 \oplus \ldots \oplus a_n x_n \oplus b\]

với \(\bm{a} = (a_1, \ldots, a_n) \in \mathbb{F}_2^n\) và \(b \in \mathbb{F}_2\) được tính theo công thức:

\[\begin{split}d(f, l_{\bm{a}, 0} (\bm{x})) & = 2^{n-1} - \frac{1}{2} W_f(\bm{a}), \\ d(f, l_{\bm{a}, 1} (\bm{x})) & = 2^{n-1} + \frac{1}{2} W_f (\bm{a}).\end{split}\]

[TODO] Câu 32

Chứng minh rằng nonlinearity của hàm Boolean \(f\) bất kì được tính bởi công thức

\[N_f = 2^{n-1} - \frac{1}{2} \max_{\bm{y}} \lvert W_f (\bm{y}) \rvert.\]

Câu 33

Chứng minh rằng hàm Boolean \(f\) là hàm bent khi và chỉ khi \(W_f(\bm{y}) = \pm 2^{n/2}\) với mọi vector \(\bm{y}\).

Câu 34

Có bao nhiêu hàm Boolean cân bằng \(n\) biến?

Trong \(2^n\) vector, ta chọn \(2^{n-1}\) vector khiến hàm Boolean có giá trị \(1\) nên đáp án là

\[C_{2^n}^{2^{n-1}}.\]

[TODO] Câu 35

Chứng minh rằng hàm Boolean \(f\) là \(r\)-resillient khi và chỉ khi nó cân bằng và correlation immune bậc \(r\).

[TODO] Câu 36 (Định lí Siegenthaler I, 1984)

Chứng minh rằng nếu hàm Boolean \(f\) là correlation immune bậc \(r\) thì \(\deg f + r \leqslant n\).

[TODO] Câu 37 (Định lí Siegenthaler II)

Chứng minh rằng nếu hàm Boolean \(f\) là \(r\)-resillient và \(r \leqslant n - 2\) thì \(\deg f + r \leqslant n - 1\).

Chứng minh cho các định lí Siegenthaler có thể tìm ở [44].

Câu 38

Chứng minh rằng hàm Boolean \(f\) là correlation immune bậc \(r\) khi và chỉ khi \(W_f(\bm{y}) = 0\) với mọi vector \(\bm{y}\) thỏa \(1 \leqslant \mathrm{wt} (\bm{y}) \leqslant r\).

Đầu tiên ta chứng minh bổ đề sau.

Bổ đề 5

Nếu hàm Boolean \(f\) là correlation immune bậc \(r\) thì nó cũng là correlation immune với mọi bậc \(s\), \(1 \leqslant s \leqslant r\).

Chứng minh bổ đề

Để chứng minh bổ đề trên ta chỉ cần chứng minh \(f\) là correlation immune bậc \(r - 1\) là đủ, từ đó quy nạp xuống tới \(1\). Gọi \(g\) là hàm con bất kì của \(f\) với \(n - r + 1\) biến (cố định \(r - 1\) biến). Khi đó khai triển \(g\) theo bất kì biến \(x_i\) nào của nó ta được

\[g = x_i g_1 \oplus (x_i \oplus 1) g_2,\]

trong đó \(g_1\) và \(g_2\) là các hàm con \(n - r\) biến. Vì \(f\) là correlation immune bậc \(r\) nên \(\operatorname{wt}(g_1) = \operatorname{wt}(g_2) = \operatorname{wt}(f)/2^r\). Ngoài ra từ (1.4) ta có

\[\operatorname{wt}(g) = \operatorname{wt}(g_1) + \operatorname{wt}(g_2) = \frac{\operatorname{wt}(f)}{2^{r-1}},\]

suy ra \(f\) là correlation bậc \(r - 1\).

Đối với điều kiện cần, Xiao và Massey [45] có một chứng minh năm 1988. Ta cần bổ đề sau.

Bổ đề 6

Biến ngẫu nhiên rời rạc \(Z\) độc lập với họ \(r\) biến ngẫu nhiên nhị phân rời rạc độc lập nhau \(Y_1\), \(Y_2\), ..., \(Y_r\) khi và chỉ khi \(Z\) độc lập với tổng \(\lambda_1 Y_1 + \lambda_2 Y_2 + \cdots + \lambda_r Y_r \in \mathbb{F}_2\) với mọi \(\lambda_1\), \(\lambda_2\), ..., \(\lambda_r\) không đồng thời bằng \(0\) và thuộc \(\mathbb{F}_2\).

Chứng minh bổ đề

Điều kiện đủ. Giả sử với hai biến ngẫu nhiên độc lập (BNN) \(Y_1\) và \(Y_2\), vì BNN \(Z\) độc lập với \(Y_1\) và \(Y_2\) nên

\[\begin{split}P(Y_1 = 0, Y_2 = 0, Z = 0) + P(Y_1 = 1, Y_2 = 1, Z = 0) & = P(Y_1 = 0) \cdot P(Y_2 = 0) \cdot P(Z = 0) + P(Y_1 = 1) \cdot P(Y_2 = 1) \cdot P(Z = 0) \\ & = \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} \\ & = \frac{1}{4} = P(Y_1 + Y_2 = 0) \cdot P(Z = 0) = P(Y_1 + Y_2 = 0, Z = 0).\end{split}\]

Chứng minh tương tự cho \(Y_1 + Y_2 = 1\) ta có

\[P(Y_1 + Y_2 = y, Z = z) = P(Y_1 + Y_2 = y) \cdot P(Z = z) \ \text{với mọi} \ y, z \in \mathbb{F}_2,\]

như vậy \(Z\) độc lập với \(Y_1 + Y_2\), và vì \(Z\) đã độc lập với \(Y_1\) và \(Y_2\) nên ta có điều phải chứng minh. Sử dụng quy nạp ta dễ dàng chứng minh \(Z\) độc lập với hệ độc lập \(m\) BNN bất kì.

Điều kiện cần. BNN rời rạc \(Z\) độc lập với tổng \(\lambda_1 Y_1 + \lambda_2 Y_2 + \cdots + \lambda_r Y_r\) với mọi \(\lambda_1\), \(\lambda_2\), ..., \(\lambda_r\) không đồng thời bằng \(0\) và thuộc \(\mathbb{F}_2\). Ta sẽ chứng minh \(Z\) độc lập với hệ độc lập \(Y_1\), \(Y_2\), ..., \(Y_r\).

Với \(m = 1\) thì điều này hiển nhiên. Với \(m = 2\), vì \(Z\) độc lập với \(Y_1\), \(Y_2\) và \(Y_1 + Y_2\) nên ta có phân bố xác suất sau với mọi giá trị \(z \in Z\): với mọi \(P(Z = z) > 0\) ta có

(9)\[\begin{split}P((Y_1 = 1, Y_2 = 1) \mid Z = z) & + P((Y_1 = 1, Y_2 = 0) \mid Z = z) \\ & = P(Y_1 = 1 \mid Z = z) = p_1, \\ P((Y_1 = 1, Y_2 = 1) \mid Z = z) & + P((Y_1 = 0, Y_2 = 1) \mid Z = z) \\ & = P(Y_2 = 1 \mid Z = z) = p_2, \\ P((Y_1 = 1, Y_2 = 0) \mid Z = z) & + P((Y_1 = 0, Y_2 = 1) \mid Z = z) \\ & = P((Y_1 + Y_2 = 1) \mid Z = z) \\ & = p_1 (1 - p_2) + (1 - p_1) p_2, \\ P((Y_1 = 1, Y_2 = 0) \mid Z = z) & + P((Y_1 = 0, Y_2 = 0) \mid Z = z) \\ & = P(Y_2 = 0 \mid Z = z) = 1 - p_2,\end{split}\]

với \(p_1 = P(Y_1 = 1)\) và \(p_2 = P(Y_2 = 1)\). Cụ thể hơn, ở phương trình đầu tiên, vì \(P(Y_1 = 1 \mid Z = z)\) không phụ thuộc \(Y_2\) nên nó là tổng khi \(Y_2 = 0\) và \(Y_2 = 1\). Tương tự cho phương trình thứ hai và thứ tư; phương trình thứ ba là khi tổng \(Y_1 + Y_2 = 1\).

Nếu xem \(4\) phương trình trên là hệ phương trình với các biến \(P((Y_1 = y_1, Y_2 = y_2) \mid Z = z)\) thì ta giải ra được

(10)\[\begin{split}P((Y_1 = 0, Y_2 = 1) \mid Z = z) & = (1 - p_1) p_2 \\ P((Y_1 = 1, Y_2 = 0) \mid Z = z) & = p_1 (1 - p_2) \\ P((Y_1 = 0, Y_2 = 0) \mid Z = z) & = (1 - p_1) (1 - p_2) \\ P((Y_1 = 1, Y_2 = 1) \mid Z = z) & = p_1 p_2.\end{split}\]

Vì \(P((Y_1 = y_1, Y_2 = y_2) \mid Z) = P(Y_1 = y_1, Y_2 = y_2)\) với mọi \(y_1, y_2 \in \mathbb{F}_2\) nên \(Z\) độc lập với họ \(Y_1\), \(Y_2\).

Giả thiết quy nạp: giả sử điều kiện đúng với mọi \(r < R\). Ta chứng minh khi \(r = R\).

Giả sử \(Z\) độc lập với tổng \(\lambda_1 Y_1 + \cdots \lambda_r Y_r\) với mọi \(\lambda_1\), ..., \(\lambda_r\) không đồng thời bằng \(0\).

Chọn \(\lambda_1 = \lambda_2 = 0\), theo giả thiết quy nạp \(Y_3\), ..., \(Y_r\), \(Z\) độc lập.

Tương tự, chọn \(\lambda_1 = 0\) thì \(Y_2\) độc lập với \(Y_3\), ..., \(Y_r\), \(Z\). Nếu chọn \(\lambda_1 = \lambda_2\) thì \(Y_1 + Y_2\) độc lập với \(Y_3\), ..., \(Y_r\), \(Z\).

Như vậy, với mọi cách chọn \(y_3\), ..., \(y_R\), \(z\), các phương trình (9) và (10) giữ nguyên sau khi đổi

\[P((Y_1 = y_1, Y_2 = y_2) \mid Z = z)\]

thành

\[P((Y_1 = y_1, Y_2 = y_2) \mid (Y_3 = y_3, \ldots, Y_R = y_R, Z = z)),\]

khi đó (10) được viết lại thành \(Y_1\), \(Y_2\) độc lập với \(Y_3\), ..., \(Y_m\), \(Z\). Như vậy \(Y_1\), \(Y_2\), ..., \(Y_m\), \(Z\) độc lập.

Ta quay lại chứng minh điều kiện cần và đủ của câu 38.

Chứng minh điều kiện đủ

Ta chứng minh: nếu \(f\) là correlation immune bậc \(r\) thì \(W_f(\bm{y}) = 0\) với mọi \(\bm{y}\) thỏa \(1 \leqslant \operatorname{wt}(\bm{y}) \leqslant r\).

Với mọi vector \(\bm{y} = (y_1, y_2, \ldots, y_n) \in \mathbb{F}_2^n\), đặt

\[S = \operatorname{supp}(\bm{y}) = \{ i : y_i = 1 \}.\]

Khi đó \(\lvert S \rvert = \operatorname{wt}(\bm{y}) = s\) với \(1 \leqslant s \leqslant r\).

Ta có

\[\begin{split}W_f(\bm{y}) & = \sum_{\bm{x} \in \mathbb{F}_2^n} (-1)^{f(\bm{x}) \oplus \langle \bm{x}, \bm{y} \rangle} \\ & = \sum_{\bm{x} \in \mathbb{F}_2^n} (-1)^{f(\bm{x}) \oplus \sum\limits_{i \in S} x_{i}}.\end{split}\]

Với mọi vector \(\bm{a} = (a_i)_{i \in S} \in \mathbb{F}_2^s\), đặt

\[E_{\bm{a}} = \{ \bm{x} \in \mathbb{F}_2^n : x_i = a_i \ \text{với mọi} \ i \in S \}.\]

Vì các vector \(\bm{x}\) trong \(E_{\bm{a}}\) được cố định \(s\) vị trí, còn \(n - s\) vị trí được chọn tùy ý, nên \(\lvert E_{\bm{a}} = 2^{n - s}\). Khi đó

\[\begin{split}W_f(\bm{y}) & = \sum_{\bm{x} \in \mathbb{F}_2^n} (-1)^{f(\bm{x}) \oplus \sum\limits_{i \in S} x_{i}} \\ & = \sum_{\bm{a} \in \mathbb{F}_2^s} \sum_{\bm{x} \in E_{\bm{a}}} (-1)^{f(\bm{x}) \oplus \sum\limits_{i \in S} a_i} \\ & = \sum_{\bm{a} \in \mathbb{F}_2^s} (-1)^{\sum\limits_{i \in S} a_i} \sum_{\bm{x} \in E_{\bm{a}}} (-1)^{f(\bm{x})}.\end{split}\]

Đặt

\[N_{\bm{a}} = \lvert \{ \bm{x} \in E_{\bm{a}} : f(\bm{x}) = 1 \} \rvert \Longrightarrow \sum_{\bm{x} \in E_{\bm{a}}} (-1)^{f(\bm{x})} = \lvert E_\bm{a} \rvert - 2 N_{\bm{a}},\]

vì \((-1)^0 = 1\) và \((-1)^1 = -1\). Hơn nữa \(N_{\bm{a}}\) là số lượng các vector \(\bm{x} \in \mathbb{F}_2^n\) mà được cố định \(s\) biến, và khiến \(f(\bm{x}) = 1\), nói cách khác là correlation immune bậc \(s\). Do đó ta có

\[N_{\bm{a}} = \frac{\operatorname{wt}(f)}{2^s} \Longrightarrow \sum_{\bm{x} \in E_{\bm{a}}} (-1)^{f(\bm{x})} = 2^{n-s} - 2 \cdot \frac{\operatorname{wt}(f)}{2^s} = 2^{n-s} - \frac{\operatorname{wt}(f)}{2^{s-1}}.\]

Đại lượng trên không phụ thuộc vào \(a\), ta gọi là \(C\). Khi đó

\[W_f(\bm{y}) = \sum_{\bm{a} \in \mathbb{F}_2^s} (-1)^{\sum\limits_{i \in S} a_i} \cdot C = C \cdot \sum_{\bm{a} \in \mathbb{F}_2^s} (-1)^{\sum\limits_{i \in S} a_i}.\]

Sử dụng tính chất (Chú ý 1.22): với vector \(\bm{z}\) cố định thì

\[\begin{split}\sum_{\bm{a} \in \mathbb{F}_2^s} (-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}\]

Trong trường hợp của chúng ta là \(\bm{z} = (1, 1, \ldots, 1) \in \mathbb{F}_2^s\) nên

\[\sum_{\bm{a} \in \mathbb{F}_2^s} (-1)^{\sum\limits_{i \in S} a_i} = 0 \Longrightarrow W_f(\bm{y}) = 0.\]

Chứng minh điều kiện cần (Xiao, Massey)

Đặt

\[\begin{split}N_{f, 0}(\bm{a}) = \lvert \{ \bm{x} \in \mathbb{F}_2^n : f(\bm{x}) = 1, \langle \bm{a}, \bm{x} \rangle = 0 \} \rvert \\ N_{f, 1}(\bm{a}) = \lvert \{ \bm{x} \in \mathbb{F}_2^n : f(\bm{x}) = 1, \langle \bm{a}, \bm{x} \rangle = 1 \} \rvert\end{split}\]

Tính chất của biến đổi Walsh-Hadamard cho ta đẳng thức

\[F(\bm{a}) = N_{f, 0}(\bm{a}) - N_{f, 1}(\bm{a}), \quad \bm{a} \in \mathbb{F}_2^n.\]

Đặt \(\bm{w} \in \mathbb{F}_2^n\) và \(\bm{X}\) là \(n\) BNN \(X_1\), \(X_2\), ..., \(X_n\). Khi đó với mọi \(\bm{w} \neq \bm{0}\) thì

\[\langle \bm{w}, \bm{X} \rangle = w_1 X_1 + w_2 X_2 + \cdots + w_n X_n\]

là tổng gồm \(\operatorname{wt}(\bm{w})\) BNN trong số \(X_1\), \(X_2\), ..., \(X_n\).

Vì tất cả \(2^{n-1}\) giá trị \(\bm{x}\) của \(\bm{X}\) mà \(\langle \bm{x}, \bm{w} \rangle = b\) bằng nhau, ta có

(11)\[P(Z = 1, \langle \bm{w}, \bm{X} \rangle = b) = 2^{-n+1} N_{f, b}(\bm{w}), \ \text{với} \ \bm{w} \neq \bm{0}\]

với \(b \in \{ 0, 1 \}\).

Quay lại bài toán, ta chứng minh nếu \(W_f(\bm{y}) = 0\) với mọi \(\bm{y}\) thỏa mãn \(1 \leqslant \operatorname{wt}(\bm{y}) \leqslant r\) thì hàm Boolean \(f(\bm{x})\) là correlation immune bậc \(r\).

Theo định nghĩa, vì \(f\) là correlation immune bậc \(r\) nên \(Z\) độc lập với mọi tập con có \(r\) phần tử hoặc ít hơn trong các BNN \(X_1\), \(X_2\), ..., \(X_n\). Khi đó, từ bổ đề trên, điều cần chứng minh tương đương với \(f\) là correlation immune bậc \(r\) khi và chỉ khi \(Z\) độc lập với mọi BNN \(\langle \bm{w}, \bm{X} \rangle\) với \(1 \leqslant \wt(\bm{w}) \leqslant r\). Từ (11), \(Z\) độc lập với \(\langle \bm{w}, \bm{X} \rangle\) khi và chỉ khi \(N_{f, 0}(\bm{w}) = N_{f, 1}(\bm{w})\) với \(1 \leqslant \wt(\bm{w}) \leqslant r\). Như vậy \(W_f(\bm{w}) = 0\) với \(1 \leqslant \wt(\bm{w}) \leqslant r\). Ta có điều phải chứng minh.

Năm 2007 Д. Г. Фон–Дер–Флаасс tìm được chặn trên cho correlation immune của hàm Boolean không cân bằng.

[TODO] Câu 39 (Định lí Д. Г. Фон–Дер–Флаасс, [46])

Gọi \(f\) là hàm Boolean không cân bằng có correlation immune bậc \(r\) khác \(0\). Chứng minh rằng \(r \leqslant (2n/3) - 1\).

[TODO] Câu 40

Chứng minh rằng với hàm Boolean \(r\)-resillient \(f\) sao cho \(r \leqslant n-2\) thì ta có bất đẳng thức \(N_f \leqslant 2^{n-1} - 2^{r+1}\) [47].

[TODO] Câu 41 (Chặn của algebraic immune)

Chứng minh rằng algebraic immune của hàm Boolean \(f\) bất kì với \(n\) biến không vượt quá giá trị \(\lceil n/2 \rceil\).

[TODO] Câu 42

Chứng minh một số tính chất cơ bản của algebraic immune với mọi hàm Boolean \(f\), \(g\) trên \(n\) biến:

• \(\mathsf{AI}(f) \leqslant \deg f\);

• \(\mathsf{AI}(f \cdot g) \leqslant \mathsf{AI}(f) + \mathsf{AI}(g)\);

• \(\mathsf{AI}(f \oplus g) \leqslant \mathsf{AI}(f) + \mathsf{AI}(g)\);

• \(\mathsf{AI}(f) = \mathsf{AI}(g)\) nếu \(g\) nhận được từ \(f\) qua một biến đổi affine trên các biến, nghĩa là \(g(\bm{x}) = f(\bm{A} \bm{x} \oplus \bm{b})\) với \(\bm{A}\) là ma trận khả nghịch bậc \(n\) và \(\bm{b}\) là vector.

[TODO] Câu 43

Xác định giá trị của \(\mathsf{AI}(f)\) với các hàm Boolean sau và tìm hàm \(g\) tương ứng:

• \(f(\bm{x}) = x_1 x_2 x_4 \oplus x_1 x_2 \oplus 1\);

• \(f(\bm{x}) = 0\);

• \(f(\bm{x}) = 1\);

• \(f(\bm{x}) = x_1 \cdots x_k\) với \(k = 1, 2, \ldots, n\);

• \(f(\bm{x}) = x_1 \oplus \ldots \oplus x_n\);

• \(f(\bm{x}) = x_1 x_2 \oplus \ldots \oplus x_{n-1} x_n\) (tổng tất cả cặp tích);

• \(f(\bm{x}) = x_1 x_2 x_3 x_4 \oplus x_5 x_6\).

[TODO] Câu 44

Cho ví dụ hàm Boolean \(f\) với giá trị algebraic immune nhỏ nhất, nghĩa là \(\mathsf{AI}(f) = d\) với \(d = 1, 2, \ldots, k\).

Câu 45

Chứng minh hàm \(S : \mathbb{F}_2^8 \to \mathbb{F}_2^8\) của S-box trong thuật toán AES là differentially \(4\)-uniform.

Bài tập này cho thấy rằng S-box tốt thì \(\delta\) sẽ nhỏ nhất có thể nhằm kháng phá mã vi sai, và có thể dễ dàng chứng minh kết quả là \(4\) bằng việc vét cạn số nghiệm của phương trình \(S(\bm{x} + \bm{a}) \oplus S(\bm{x}) = \bm{b}\) với mọi \(\bm{a} \in \mathbb{F}_2^8\) khác không và với mọi \(\bm{b} \in \mathbb{F}_2^8\).