Phân loại hàm boolean có ý nghĩa gì trong an toàn thông tin?

Phân loại hàm boolean giúp nhận diện các lớp hàm có độ phi tuyến cao, bậc đại số lớn và tính miễn dịch tương quan tốt để chống lại các đòn tấn công thám mã vi sai, tuyến tính và đại số.

Hàm bent là gì và tại sao chỉ tồn tại ở số biến chẵn?

Hàm bent là hàm Boolean có khoảng cách phi tuyến cực đại tới mọi hàm afin, phổ Walsh có độ lớn tuyệt đối không đổi tại mọi điểm và điều kiện trực giao phổ đòi hỏi số chiều không gian vector phải là số chẵn.

Định lý Siegenthaler thiết lập mối quan hệ đánh đổi nào?

Định lý Siegenthaler chỉ ra rằng một hàm Boolean cân bằng n biến không thể đồng thời đạt bậc đại số cực đại và bậc miễn dịch tương quan cực đại mà bị ràng buộc bởi bất đẳng thức tổng bậc đối với mọi bậc miễn dịch tương quan nhỏ hơn n trừ một.

Hai hàm Boolean tương đương afin khi nào?

Hai hàm tương đương afin khi hàm này có thể biến đổi thành hàm kia thông qua một phép thế biến đổi tọa độ afin khả nghịch và có thể cộng thêm một hằng số nhị phân.

Phân loại hàm boolean là gì? Cơ sở toán học và ứng dụng

Phân loại hàm boolean là quá trình phân chia tập hợp các hàm đại số logic nhị phân thành các lớp tương đương rời nhau dựa trên các bất biến đại số, nhóm tự đẳng cấu không gian hoặc các chỉ số mật mã đặc trưng. Trong toán học rời rạc và lý thuyết thông tin, một hàm Boolean $n$ biến là một ánh xạ có dạng $f: \mathbb{F}_2^n \to \mathbb{F}_2$ , trong đó $\mathbb{F}_2 = \{0, 1\}$ là trường hữu hạn gồm hai phần tử. Do không gian hàm Boolean tăng trưởng bùng nổ theo kích thước $2^{2^n}$ , việc tìm kiếm và tối ưu hóa thủ công từng hàm đơn lẻ khi số biến gia tăng là bất khả thi. Các phương pháp phân loại cấu trúc đóng vai trò cốt lõi trong việc nhận diện các lớp hàm có tính chất tối ưu phục vụ xây dựng mã sửa sai và bảo vệ các hệ mật mã hiện đại.

Cơ sở biểu diễn toán học của hàm Boolean

Để tiến hành phân loại một cách đại số, mỗi hàm Boolean có thể được mô tả qua nhiều dạng biểu diễn tương đương với những ưu thế tính toán riêng biệt.

Bảng chân lý và vector chân trị

Dạng biểu diễn cơ bản nhất của một hàm Boolean $f$ trên không gian $n$ biến là bảng chân trị liệt kê toàn bộ các giá trị đầu ra tại các điểm đầu vào nhị phân được sắp xếp theo thứ tự từ điển. Vector chân trị ký hiệu là $v_f = (f(v_0), f(v_1), \dots, f(v_{2^n-1}))$ . Trọng số Hamming của hàm, ký hiệu là $wt(f)$ , được định nghĩa là số lượng phần tử nhận giá trị bằng một trong vector chân trị. Một hàm được gọi là cân bằng khi và chỉ khi trọng số Hamming bằng một nửa kích thước không gian vector đầu vào, tức là $wt(f) = 2^{n-1}$ .

Dạng chuẩn đại số

Mỗi hàm Boolean $n$ biến đều có thể biểu diễn duy nhất dưới dạng đa thức nhiều biến trên trường hữu hạn $\mathbb{F}_2$ , được gọi là dạng chuẩn đại số (ANF):

f(x_1, \dots, x_n) = \bigoplus_{u \in \mathbb{F}_2^n} a_u \prod_{i=1}^n x_i^{u_i}

Trong biểu thức trên, các hệ số $a_u \in \mathbb{F}_2$ và phép cộng là phép cộng modulo hai. Bậc đại số của hàm $f$ , ký hiệu là $\deg(f)$ , là bậc lớn nhất của các đơn thức có hệ số khác không trong dạng chuẩn đại số. Các hàm có bậc đại số không vượt quá một ( $\deg(f) \le 1$ ) được gọi là hàm afin; nếu không chứa hệ số tự do thì hàm được gọi là hàm tuyến tính.

Biến đổi Walsh-Hadamard và phân tích phổ

Biến đổi Fourier nhị phân hay biến đổi Walsh-Hadamard là công cụ giải tích then chốt để khảo sát các tính chất tương quan của hàm Boolean. Hệ số Walsh của hàm $f$ tại điểm $\omega \in \mathbb{F}_2^n$ được xác định theo công thức:

W_f(\omega) = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) \oplus \omega \cdot x}

Trong đó $\omega \cdot x = \bigoplus_{i=1}^n \omega_i x_i$ là tích vô hướng thông thường trên trường nhị phân. Tập hợp tất cả các giá trị của hệ số Walsh trên toàn không gian được gọi là phổ Walsh của hàm. Độ phi tuyến của hàm Boolean, biểu thị khoảng cách Hamming ngắn nhất từ hàm $f$ tới tập hợp tất cả các hàm afin, được tính thông qua đỉnh cực đại của phổ Walsh:

NL(f) = 2^{n-1} - \frac{1}{2} \max_{\omega \in \mathbb{F}_2^n} |W_f(\omega)|

Phân loại theo quan hệ tương đương đại số

Quan hệ tương đương giữa các hàm cho phép gom các hàm có cùng cấu trúc cốt lõi vào chung một lớp đại diện, giúp giảm thiểu đáng kể độ phức tạp khi nghiên cứu không gian hàm.

Tương đương afin

Hai hàm Boolean $f$ và $g$ trên không gian $n$ biến được gọi là tương đương afin chuẩn nếu tồn tại một phép biến đổi afin khả nghịch $A(x) = M \cdot x \oplus b$ trên $\mathbb{F}_2^n$ , với $M$ là ma trận nhị phân không suy biến, $b \in \mathbb{F}_2^n$ và hằng số $c \in \{0, 1\}$ sao cho:

g(x) = f(A(x)) \oplus c

Quan hệ tương đương afin bảo toàn các chỉ số quan trọng bao gồm bậc đại số, phổ Walsh tổng quát và độ phi tuyến của hàm. Trong lý thuyết mã sửa sai, Berlekamp và Welch năm 1972 đã phân tích cấu trúc các lớp kề của mã Reed-Muller bậc một với độ dài 32 ký hiệu. Kết quả giải tích này đã hoàn tất việc phân loại toàn diện không gian hàm Boolean 5 biến thành đúng 48 lớp tương đương afin cơ bản modulo không gian hàm afin.

Mở rộng tương đương afin và tương đương CCZ

Ngoài tương đương afin kinh điển, trong thiết kế các hàm vector và hộp thế phi tuyến (S-box), các nhà nghiên cứu áp dụng các quan hệ tương đương rộng hơn:

Tương đương afin mở rộng (EA-equivalence): Hai hàm $f$ và $g$ được gọi là tương đương EA nếu tồn tại phép biến đổi afin khả nghịch $A(x)$ và một hàm afin tuyến tính $l(x)$ sao cho $g(x) = f(A(x)) \oplus l(x)$ . Phép biến đổi này bảo toàn tính chất vi sai và độ phi tuyến.
Tương đương Carlet-Charpin-Zinoviev (CCZ-equivalence): Hai hàm được gọi là tương đương CCZ nếu đồ thị tọa độ của chúng tương đương afin với nhau trên không gian tích. Đây là quan hệ tổng quát nhất bảo toàn đồng thời phổ Walsh và bảng phân phối vi sai của hàm.

Phân loại theo tiêu chuẩn mật mã học

Trong ứng dụng an toàn thông tin, các hàm Boolean được phân loại theo khả năng chống lại các dạng tấn công thám mã vi sai, tuyến tính và đại số.

Lớp hàm Bent và tính phi tuyến cực đại

Hàm bent là lớp hàm Boolean đạt khoảng cách xa nhất tới toàn bộ không gian các hàm afin. Nghiên cứu nền tảng của Rothaus công bố năm 1976 đã chứng minh rằng các hàm bent chỉ có thể tồn tại khi số biến $n$ là một số chẵn. Đặc trưng phổ của hàm bent là độ lớn tuyệt đối của mọi hệ số Walsh đều bằng nhau tại mọi điểm:

|W_f(\omega)| = 2^{n/2}, \quad \forall \omega \in \mathbb{F}_2^n

Do phổ Walsh có giá trị tuyệt đối không đổi, hàm bent đạt độ phi tuyến cực đại bằng $2^{n-1} - 2^{(n/2) - 1}$ . Tuy nhiên, do tính chất phổ đặc biệt này, các hàm bent không bao giờ cân bằng, vì vậy chúng không thể dùng trực tiếp làm hàm kết hợp trong mật mã dòng mà thường được dùng làm khối xây dựng cho các cấu trúc phức hợp hơn. Tổng quan của Cusick và Stanica năm 2017 đã hệ thống hóa các phương pháp sinh hàm bent như phép dựng Maiorana-McFarland, lớp hàm Dillon partial spread (lớp trải một phần) và các hàm bent lũy thừa.

Lớp hàm miễn dịch tương quan

Để ngăn chặn các đòn tấn công tương quan vào bộ tạo khóa dòng sử dụng thanh ghi dịch phản hồi tuyến tính, các hàm thành phần cần thỏa mãn điều kiện độc lập thống kê với các tập con biến đầu vào. Nghiên cứu của Siegenthaler năm 1984 đã đưa ra định nghĩa chính xác về tính miễn dịch tương quan bậc $m$ : phân phối xác suất đầu ra của hàm không đổi khi bất kỳ tập hợp con gồm $m$ biến đầu vào nào bị cố định.

Định lý bất đẳng thức Siegenthaler thiết lập một ranh giới cân bằng ràng buộc giữa bậc đại số $d$ và bậc miễn dịch tương quan $m$ của hàm $n$ biến. Đối với các hàm Boolean cân bằng, nếu bậc miễn dịch tương quan thỏa mãn $1 \le m \le n - 2$ , bất đẳng thức có dạng:

d \le n - m - 1

Khi bậc miễn dịch tương quan đạt giá trị tới hạn $m = n - 1$ , hàm cân bằng bắt buộc phải có bậc đại số $d = 1$ , tiêu biểu là các hàm chẵn lẻ tuyến tính. Ràng buộc lý thuyết này chỉ ra rằng một hàm Boolean không thể đồng thời đạt bậc đại số cực đại và bậc miễn dịch tương quan cực đại, đòi hỏi người thiết kế phải lựa chọn điểm đánh đổi tối ưu phù hợp với kiến trúc mật mã.

Tiêu chuẩn thác nghiêm ngặt

Khả năng khuếch tán dữ liệu là tiêu chí thiết yếu để bảo vệ mật mã khối trước các kỹ thuật thám mã vi sai. Webster và Tavares năm 1986 đã hình thức hóa tiêu chuẩn thác nghiêm ngặt (SAC). Một hàm Boolean thỏa mãn tiêu chuẩn này nếu việc đảo ngược giá trị của một bit đầu vào bất kỳ luôn dẫn đến sự biến đổi giá trị bit đầu ra với xác suất đúng bằng 0,5:

P(f(x) \oplus f(x \oplus e_i) = 1) = 0,5

Trong đó $e_i$ là vector đơn vị nhị phân có giá trị một tại vị trí thứ $i$ . Tiêu chuẩn SAC đảm bảo tính ngẫu nhiên thống kê cao của các hàm thành phần trong các hộp thế S-box.

Bảng tổng hợp các lớp hàm Boolean đặc trưng

Dưới đây là bảng đối chiếu các đặc tính cấu trúc chính giữa các lớp hàm Boolean thường gặp trong ứng dụng lý thuyết mã và mật mã học:

Lớp hàm	Tính cân bằng	Đặc trưng cấu trúc và miền phổ	Ứng dụng chủ đạo
Hàm tuyến tính và afin	Cân bằng (trừ hàm hằng)	Chỉ có một điểm phổ nhận giá trị cực đại	Lý thuyết mã hóa, thanh ghi LFSR
Hàm Bent	Không cân bằng	Mọi điểm phổ có độ lớn tuyệt đối đồng nhất	Mật mã khối, chuỗi trực giao, hàm phi tuyến
Hàm miễn dịch tương quan	Có thể cân bằng hoặc không	Các hệ số Walsh bằng không trong phạm vi bậc	Mật mã dòng chống thám mã tương quan
Hàm thỏa mãn tiêu chuẩn SAC	Thường được thiết kế cân bằng	Đạo hàm Boolean theo các vector cơ sở là hàm cân bằng	Hộp thế S-box trong mật mã khối và hàm băm

Ứng dụng phân loại hàm trong mật mã hiện đại

Trong mật mã học hiện đại, việc phân loại hàm Boolean là bước chuẩn bị then chốt trong quy trình đánh giá độ an toàn của các chuẩn mật mã quốc tế. Các hàm băm và thuật toán mã khối hiện đại đòi hỏi thành phần phi tuyến phải có bậc đại số đủ cao để chống lại các đòn thám mã đại số và thám mã đa thức.

Trong phân tích cấu trúc thuật toán băm chuẩn quốc gia SHA-3 của Hoa Kỳ, nghiên cứu của Nguyễn Văn Long và Lê Duy Đức năm 2020 đã khảo sát chuyên sâu bậc đại số của các thành phần hoán vị phi tuyến trong lõi Keccak. Nghiên cứu đã chứng minh tầm quan trọng của việc kiểm soát bậc đại số của các hàm thành phần, từ đó đề xuất các cấu trúc hộp thế 5-bit có bậc đại số cao nhằm gia tăng độ an toàn cho các hoán vị mật mã trước các đòn tấn công đại số.

Thuật toán phân lớp và thách thức tính toán

Việc phân loại đầy đủ không gian hàm Boolean ở số biến lớn gặp phải rào cản tính toán do hiện tượng bùng nổ tổ hợp. Với số biến nhỏ, các nhà toán học đã hoàn tất việc liệt kê các lớp tương đương afin nhờ các kỹ thuật duyệt cây và bất biến phổ. Tuy nhiên, khi số biến vượt quá các ngưỡng nhỏ, bài toán kiểm tra tính tương đương afin giữa hai hàm tùy ý trở thành bài toán có độ phức tạp cao, tương đương với bài toán đẳng cấu đồ thị.

Để giải quyết thách thức này, các nghiên cứu đương đại tập trung vào việc thu hẹp không gian tìm kiếm thông qua các lớp hàm con có cấu trúc đặc biệt như hàm đối xứng quay (rotation symmetric) hoặc khai thác các thuật toán tìm kiếm nghiệm đại số kết hợp trí tuệ nhân tạo. Những nỗ lực này tiếp tục đóng góp vào việc mở rộng hiểu biết về biên giới cấu trúc của các hàm Boolean trong thế kỷ thông tin lượng tử.