1.3. Biểu diễn hàm Boolean vectorial

1.3.1. Hàm tọa độ và ANF

Một hàm \((n,m)\) là ánh xạ

\[F : \mathbb{F}_2^n \longrightarrow \mathbb{F}_2^m, \qquad F = (f_1, \ldots, f_m),\]

trong đó \(f_1, \ldots, f_m\) là các hàm Boolean tọa độ.

Bảng chân trị của \(F\) thu được bằng cách ghép các cột bảng chân trị của những hàm tọa độ:

\(\bm{x}\)	\(f_1(\bm{x})\)	\(f_2(\bm{x})\)	\(\cdots\)	\(f_m(\bm{x})\)
\((0,\ldots,0)\)	\(f_1(0,\ldots,0)\)	\(f_2(0,\ldots,0)\)	\(\cdots\)	\(f_m(0,\ldots,0)\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\vdots\)
\((1,\ldots,1)\)	\(f_1(1,\ldots,1)\)	\(f_2(1,\ldots,1)\)	\(\cdots\)	\(f_m(1,\ldots,1)\)

Các quan hệ \(x_i^2=x_i\) cho phép đồng nhất vành hàm Boolean với vành thương

\[\mathcal{B}_n = \frac{\mathbb{F}_2[x_1,\ldots,x_n]} {\langle x_1^2+x_1,\ldots,x_n^2+x_n\rangle}.\]

Vì thế mỗi lớp có duy nhất một đại diện multilinear, tức mỗi biến xuất hiện với số mũ không quá \(1\).

Định nghĩa 1.67 (ANF của hàm vectorial)

Algebraic normal form của \(F\) là biểu diễn duy nhất

\[F(\bm{x}) = \sum_{I \subseteq [n]} \bm{a}_I \prod_{i \in I} x_i = \sum_{I \subseteq [n]} \bm{a}_I \bm{x}^I,\]

trong đó \(\bm{a}_I \in \mathbb{F}_2^m\) và tổng được tính theo từng tọa độ trong \(\mathbb{F}_2^m\).

Với \(\bm{u} \in \mathbb{F}_2^n\), đặt

\[\bm{x}^{\bm{u}} = \prod_{j \in [n]} x_j^{u_j}, \qquad \operatorname{supp}(\bm{u}) = \{j \in [n] : u_j = 1\}.\]

Khi đó cũng có thể viết

\[F(\bm{x}) = \sum_{\bm{u} \in \mathbb{F}_2^n} \bm{a}_{\bm{u}} \bm{x}^{\bm{u}}.\]

Nếu \(\bm{u} \lor \bm{v}\) là phép OR theo từng tọa độ thì, trong vành các hàm Boolean,

\[\bm{x}^{\bm{u}} \bm{x}^{\bm{v}} = \bm{x}^{\bm{u} \lor \bm{v}}, \qquad \operatorname{supp}(\bm{u} \lor \bm{v}) = \operatorname{supp}(\bm{u}) \cup \operatorname{supp}(\bm{v}).\]

Từ công thức ANF suy ra

\[F(\bm{x}) = \sum_{I \subseteq \operatorname{supp}(\bm{x})} \bm{a}_I.\]

1.3.2. Phép đảo Möbius cho hệ số

Định lý 1.17 (Công thức hệ số ANF)

Với mọi \(I \subseteq [n]\), hệ số ANF của \(F\) là

\[\begin{split}\bm{a}_I = \sum_{\substack{\bm{x} \in \mathbb{F}_2^n \\ \operatorname{supp}(\bm{x}) \subseteq I}} F(\bm{x}).\end{split}\]

Tổng được tính trong \(\mathbb{F}_2^m\). Với \(m=1\), đây chính là công thức biến đổi Möbius của hàm Boolean.

Chứng minh

Đặt vế phải là \(\bm{b}_I\) và xét \(G(\bm{x}) = \sum_I \bm{b}_I \bm{x}^I\). Khi đổi thứ tự hai tổng, hệ số của \(F(\bm{y})\) trong \(G(\bm{x})\) là số tập \(I\) thỏa

\[\operatorname{supp}(\bm{y}) \subseteq I \subseteq \operatorname{supp}(\bm{x}).\]

Nếu \(\bm{y} \npreccurlyeq \bm{x}\) thì không có tập nào. Nếu \(\bm{y} \preccurlyeq \bm{x}\), số tập như vậy là

\[2^{\mathrm{wt}(\bm{x}) - \mathrm{wt}(\bm{y})}.\]

Số này lẻ khi và chỉ khi \(\bm{x}=\bm{y}\). Vì tổng được tính trong đặc số \(2\), suy ra \(G(\bm{x})=F(\bm{x})\); tính duy nhất của ANF cho \(\bm{a}_I=\bm{b}_I\).

1.3.3. Indicator của đồ thị

Với đồ thị

\[\mathcal{G}_F = \{(\bm{x},F(\bm{x})) : \bm{x} \in \mathbb{F}_2^n\},\]

đặt \(\mathbf{1}_{\mathcal{G}_F}\) là hàm Boolean trên \(\mathbb{F}_2^{n+m}\) nhận giá trị \(1\) đúng tại các điểm thuộc \(\mathcal{G}_F\).

Tính chất 1.3 (ANF của graph indicator)

Nếu \(F=(f_1,\ldots,f_m)\) thì

\[\mathbf{1}_{\mathcal{G}_F}(\bm{x},\bm{y}) = \prod_{j \in [m]} (y_j \oplus f_j(\bm{x}) \oplus 1)\]

và do đó

\[\mathbf{1}_{\mathcal{G}_F}(\bm{x},\bm{y}) = \bigoplus_{J \subseteq [m]} \bm{y}^J \prod_{j \in [m] \setminus J} (f_j(\bm{x}) \oplus 1).\]

Thật vậy, với hai vector \(\bm{y},\bm{y}' \in \mathbb{F}_2^m\), ta có

\[\prod_{j \in [m]} (y_j \oplus y'_j \oplus 1) = 1 \quad\Longleftrightarrow\quad \bm{y}=\bm{y}'.\]

Hệ số của đơn thức \(\bm{x}^I \bm{y}^J\) trong graph indicator là

\[a_{I,J} = \left| \left\{\bm{x} \in \mathbb{F}_2^n : \operatorname{supp}(\bm{x}) \subseteq I, \operatorname{supp}(F(\bm{x})) \subseteq J \right\} \right| \pmod 2.\]

Nếu \(F\) là một hoán vị của \(\mathbb{F}_2^n\), đồ thị của hàm nghịch đảo thu được bằng cách đổi chỗ hai tọa độ:

\[\mathbf{1}_{\mathcal{G}_F}(\bm{x},\bm{y}) = \mathbf{1}_{\mathcal{G}_{F^{-1}}}(\bm{y},\bm{x}).\]

Graph indicator cũng biểu diễn phép hợp thành. Nếu \(F : \mathbb{F}_2^n \to \mathbb{F}_2^m\) và \(G : \mathbb{F}_2^m \to \mathbb{F}_2^r\) thì

\[\mathbf{1}_{\mathcal{G}_{G \circ F}}(\bm{x},\bm{z}) = \bigoplus_{\bm{y} \in \mathbb{F}_2^m} \mathbf{1}_{\mathcal{G}_F}(\bm{x},\bm{y}) \mathbf{1}_{\mathcal{G}_G}(\bm{y},\bm{z}).\]

1.3.4. Bậc đại số

Định nghĩa 1.68 (Bậc của hàm vectorial)

Bậc đại số của \(F\) là

\[\deg(F) = \max\{|I| : I \subseteq [n],\ \bm{a}_I \neq \bm{0}\}.\]

Tương đương,

\[\deg(F) = \max_{j \in [m]} \deg(f_j).\]

Nếu viết

\[\mathbf{1}_{\mathcal{G}_F}(\bm{x},\bm{y}) = \bigoplus_{J \subseteq [m]} \varphi_J(\bm{x}) \bm{y}^J,\]

thì hệ số ứng với \(|J|=m-1\) chính là một hàm tọa độ của \(F\) hoặc bù của nó. Vì vậy

\[\deg(F) = \max_{|J|=m-1} \deg(\varphi_J).\]

Ngoài ra,

\[\deg(\mathbf{1}_{\mathcal{G}_F}) = \max_{J \subseteq [m]} \left( \deg\!\left(\prod_{j \in [m] \setminus J}(f_j \oplus 1)\right) + |J| \right),\]

nên

\[\deg(\mathbf{1}_{\mathcal{G}_F}) \geqslant \max\{m,\,m-1+\deg(F)\}.\]

Graph indicator còn cho các chặn bậc hữu ích đối với phép hợp thành. Với

\[F : \mathbb{F}_2^n \to \mathbb{F}_2^m, \qquad G : \mathbb{F}_2^m \to \mathbb{F}_2^r,\]

ta có chặn Carlet

\[\deg(G \circ F) \leqslant \deg(\mathbf{1}_{\mathcal{G}_F}) + \deg(G) - m.\]

Tổng quát hơn, nếu \(H : \mathbb{F}_2^r \to \mathbb{F}_2^s\) thì

\[\deg(H \circ G \circ F) \leqslant \deg(\mathbf{1}_{\mathcal{G}_F}) + \deg(\mathbf{1}_{\mathcal{G}_G}) + \deg(H) - m - r.\]

1.3.5. Biểu diễn đơn biến

Sau khi đồng nhất không gian vector \(\mathbb{F}_2^n\) với trường \(\mathbb{F}_{2^n}\), mọi ánh xạ \(F : \mathbb{F}_{2^n} \to \mathbb{F}_{2^n}\) có biểu diễn đa thức duy nhất

\[F(x) = \sum_{i=0}^{2^n-1} \delta_i x^i,\]

với \(\delta_i \in \mathbb{F}_{2^n}\). Đây được gọi là biểu diễn đơn biến của \(F\). Ta cũng có thể xem nó là một phần tử của

\[\mathbb{F}_{2^n}[X] / (X^{2^n} + X),\]

vì mọi phần tử của \(\mathbb{F}_{2^n}\) đều thỏa \(x^{2^n}=x\).

1.3.5.1. Trường hợp hàm Boolean

Một đa thức đơn biến

\[f(x)=\sum_{i=0}^{2^n-1}\delta_i x^i\]

nhận giá trị trong \(\mathbb{F}_2\) khi và chỉ khi \(f(x)^2=f(x)\) với mọi \(x \in \mathbb{F}_{2^n}\). Do ánh xạ \(x \mapsto x^2\) là tự đẳng cấu Frobenius, điều kiện này tương đương với

\[\sum_{i=0}^{2^n-1}\delta_i^2 X^{2i} \equiv \sum_{i=0}^{2^n-1}\delta_i X^i \pmod{X^{2^n}+X}.\]

Suy ra

\[\delta_0,\delta_{2^n-1} \in \mathbb{F}_2, \qquad \delta_{2i \bmod (2^n-1)}=\delta_i^2\]

với mọi \(i \in \{1,\ldots,2^n-2\}\).

1.3.6. Các quan hệ tương đương

Các quan hệ tương đương cho phép phân loại những hàm vectorial chỉ khác nhau bởi phép đổi tọa độ hoặc đổi biểu diễn.

Định nghĩa 1.69 (Tương đương hoán vị)

Một hoán vị \(\sigma\in\mathfrak{S}_n\) tác động lên \(\mathbb{F}_2^n\) bởi

\[\sigma(x_1,\ldots,x_n) =(x_{\sigma(1)},\ldots,x_{\sigma(n)}).\]

Hai hàm \((n,m)\) là \(F\) và \(G\) tương đương hoán vị nếu tồn tại \(\sigma\in\mathfrak{S}_n\) và \(\tau\in\mathfrak{S}_m\) sao cho

\[G=\tau\circ F\circ\sigma.\]

Định nghĩa 1.70 (Tương đương tuyến tính)

Hai hàm \(F\) và \(G\) tương đương tuyến tính nếu

\[G=L'\circ F\circ L,\]

trong đó \(L\) và \(L'\) là các tự đẳng cấu tuyến tính của miền xác định và miền giá trị. Viết vector dưới dạng hàng, \(L(\bm{x})=\bm{x}M\) với \(M\in\operatorname{GL}(n,2)\).

Định nghĩa 1.71 (Tương đương affine)

Hai hàm \(F\) và \(G\) tương đương affine nếu

\[G=A'\circ F\circ A,\]

trong đó \(A\) và \(A'\) là các hoán vị affine. Chẳng hạn,

\[A(\bm{x})=\bm{x}M+\bm{a}, \qquad M\in\operatorname{GL}(n,2).\]

Định nghĩa 1.72 (Tương đương affine mở rộng)

Hai hàm \(F\) và \(G\) tương đương affine mở rộng (extended-affine equivalent, hay EA-equivalent) nếu

\[G=A'\circ F\circ A+A'',\]

trong đó \(A,A'\) là các hoán vị affine và \(A'' : \mathbb{F}_2^n\to\mathbb{F}_2^m\) là hàm affine tùy ý,

\[A''(\bm{x})=\bm{x}M''+\bm{b}.\]

1.3.6.1. Tương đương CCZ

Định nghĩa 1.73 (Tương đương CCZ)

Hai hàm \(F,G : \mathbb{F}_2^n\to\mathbb{F}_2^m\) tương đương CCZ (Carlet--Charpin--Zinoviev equivalent) nếu tồn tại một hoán vị affine \(\mathcal{L}\) của \(\mathbb{F}_2^{n+m}\) sao cho

\[\mathcal{G}_G=\mathcal{L}(\mathcal{G}_F).\]

Viết

\[\mathcal{L}(\bm{x},\bm{y}) =\bigl(L_1(\bm{x},\bm{y}),L_2(\bm{x},\bm{y})\bigr),\]

trong đó \(L_1\) nhận giá trị trong \(\mathbb{F}_2^n\) và \(L_2\) nhận giá trị trong \(\mathbb{F}_2^m\). Đặt

\[F_1(\bm{x})=L_1(\bm{x},F(\bm{x})), \qquad F_2(\bm{x})=L_2(\bm{x},F(\bm{x})).\]

Ảnh \(\mathcal{L}(\mathcal{G}_F)\) là đồ thị của một hàm khi và chỉ khi \(F_1\) là hoán vị của \(\mathbb{F}_2^n\). Khi đó

\[G=F_2\circ F_1^{-1}.\]

Nếu hai phép biến đổi CCZ của cùng \(F\) có chung \(L_1\) nhưng khác \(L_2\), hai hàm thu được là EA-equivalent. Riêng với một hoán vị \(F\), phép đổi chỗ hai thành phần của đồ thị cho thấy \(F\) và \(F^{-1}\) luôn CCZ-equivalent.

Các quan hệ tạo thành chuỗi kéo theo

\[\text{hoán vị} \Longrightarrow\text{tuyến tính} \Longrightarrow\text{affine} \Longrightarrow\text{EA} \Longrightarrow\text{CCZ}.\]

Nhìn chung các chiều đảo lại không đúng.

Định nghĩa 1.74 (Bất biến theo một quan hệ tương đương)

Một tính chất hoặc tham số được gọi là bất biến đối với một quan hệ tương đương nếu nó có cùng giá trị trên mọi hàm thuộc cùng một lớp tương đương.