1.5. Các tính chất mật mã của hàm Boolean

Hàm Boolean là thành phần trung tâm của nhiều stream cipher, còn hàm Boolean vectorial xuất hiện tự nhiên dưới dạng S-box trong block cipher. Các tính chất dưới đây đo khả năng chống lại những lớp tấn công khác nhau; trong thực tế thường phải cân bằng nhiều tiêu chí thay vì tối ưu riêng một tiêu chí.

1.5.1. Bậc đại số

Bậc đại số \(\deg(f)\) nên đủ cao để cản trở việc biểu diễn hệ mật bằng các phương trình bậc thấp. Điều này đặc biệt quan trọng trong stream cipher sử dụng LFSR và trong các tấn công đại số.

1.5.2. Nonlinearity

Nonlinearity đo khoảng cách từ hàm Boolean tới tập hàm affine và là một chỉ báo quan trọng đối với khả năng chống phân tích tuyến tính. Công thức qua phổ Walsh, bound cực đại và hàm Bent được trình bày tại Chú ý 1.24.

Với \(n\) chẵn,

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

Dấu bằng xảy ra đúng với các hàm Bent. Hàm Bent không cân bằng, nên không thể đồng thời đạt nonlinearity cực đại và tính cân bằng.

1.5.3. Tính cân bằng

Theo Định nghĩa 1.61, hàm \(f : \mathbb{F}_2^n \to \mathbb{F}_2\) cân bằng khi \(\mathrm{wt}(f)=2^{n-1}\). Điều kiện này tránh thiên lệch thống kê trực tiếp ở đầu ra. Theo tính chất của phổ Walsh, nó tương đương với \(W_f(\bm{0})=0\).

Bài tập. Xác định số lượng hàm Boolean cân bằng có \(n\) biến. Lời giải được trình bày trong phần đáp án bài tập sách của notebook Contests.

1.5.4. Kháng tương quan và resiliency

Định nghĩa 1.76 (Kháng tương quan bậc \(r\))

Hàm Boolean \(f\) là correlation-immune bậc \(r\) nếu đầu ra của nó độc lập thống kê với mọi tập gồm không quá \(r\) biến đầu vào.

Tương đương, với mọi \(I \subseteq [n]\), \(|I| \leqslant r\), và mọi phép gán \(\bm{a} \in \mathbb{F}_2^{|I|}\), restriction \(f_I^{\bm{a}}\) thỏa

\[\mathrm{wt}(f_I^{\bm{a}}) = \frac{\mathrm{wt}(f)}{2^{|I|}}.\]

Định nghĩa 1.77 (Hàm \(r\)-resilient)

Hàm \(f\) được gọi là :math:`r`-resilient nếu nó vừa cân bằng vừa correlation-immune bậc \(r\). Tương đương, mọi hàm con thu được bằng cách cố định không quá \(r\) biến đều cân bằng.

Resiliency là tiêu chí quan trọng đối với hàm kết hợp trong stream cipher vì giúp chống correlation attack.

1.5.5. Kháng đại số

Định nghĩa 1.78 (Algebraic immunity)

Algebraic immunity của \(f\), kí hiệu \(\mathsf{AI}(f)\), là số nguyên nhỏ nhất \(d\) sao cho tồn tại hàm Boolean \(g \neq 0\) với \(\deg(g)=d\) và

\[fg=0\]

hoặc

\[(f \oplus 1)g=0.\]

Hàm \(g\) được gọi là một annihilator của \(f\) hoặc \(f \oplus 1\). Algebraic immunity càng cao thì càng khó dựng quan hệ đại số bậc thấp phục vụ fast algebraic attack.

Ví dụ 1.46

Với

\[f(\bm{x}) = x_1x_2x_3 \oplus x_1,\]

chọn \(g(\bm{x})=x_1\oplus1\). Khi đó

\[fg=x_1(x_2x_3\oplus1)(x_1\oplus1)=0,\]

nên \(\mathsf{AI}(f)=1\).

1.5.6. Differential uniformity

Định nghĩa 1.79 (Differential \(\delta\)-uniformity)

Hàm \(F : \mathbb{F}_p^n \to \mathbb{F}_p^m\) được gọi là differentially :math:`delta`-uniform nếu, với mọi \(\bm{a} \in \mathbb{F}_p^n \setminus \{\bm{0}\}\) và \(\bm{b} \in \mathbb{F}_p^m\), phương trình

\[F(\bm{x}+\bm{a})-F(\bm{x})=\bm{b}\]

có không quá \(\delta\) nghiệm \(\bm{x}\).

Số \(\delta\) càng nhỏ thì phân phối sai khác đầu ra càng đều và S-box càng ít để lộ đặc trưng cho phân tích vi sai. Trong trường hợp nhị phân,

\[F(\bm{x}+\bm{a})-F(\bm{x}) =F(\bm{x}\oplus\bm{a})\oplus F(\bm{x}).\]

Nếu \(\bm{x}\) là nghiệm thì \(\bm{x}\oplus\bm{a}\) cũng là nghiệm, nên differential uniformity của một hàm nhị phân không hằng theo đạo hàm luôn là số chẵn.

1.5.6.1. Perfect nonlinear và almost perfect nonlinear

Định nghĩa 1.80 (Hàm perfect nonlinear)

Hàm \(F : \mathbb{F}_p^n \to \mathbb{F}_p^m\) được gọi là perfect nonlinear (PN) nếu, với mọi \(\bm{a}\neq\bm{0}\) và mọi \(\bm{b}\), phương trình sai khác có đúng \(p^{n-m}\) nghiệm.

Khi \(n=m\), điều này tương đương differential \(1\)-uniformity. Vì nghiệm trong trường hợp nhị phân nghiệm đi thành cặp, không tồn tại hàm PN từ \(\mathbb{F}_2^n\) tới chính nó.

Định nghĩa 1.81 (Hàm almost perfect nonlinear)

Hàm nhị phân vectorial \(F : \mathbb{F}_2^n \to \mathbb{F}_2^m\) được gọi là almost perfect nonlinear (APN) nếu nó differentially \(2\)-uniform, tức mỗi phương trình

\[F(\bm{x}\oplus\bm{a})\oplus F(\bm{x})=\bm{b}\]

có không quá hai nghiệm khi \(\bm{a}\neq\bm{0}\).

Việc xây dựng các hoán vị APN trong số biến chẵn là một bài toán quan trọng, đặc biệt đối với kích thước S-box là lũy thừa của \(2\).

1.5.6.2. Almost Bent

Với \(n\) lẻ, một hàm vectorial \(F : \mathbb{F}_2^n \to \mathbb{F}_2^n\) được gọi là Almost Bent (AB) nếu mọi component \(\langle\bm{b},F\rangle\), \(\bm{b}\neq\bm{0}\), có phổ Walsh thuộc

\[\{0,\,\pm 2^{(n+1)/2}\}.\]

Khi đó nonlinearity vectorial đạt

\[N_F=2^{n-1}-2^{(n-1)/2}.\]