Bộ phân biệt cấu trúc mới đối với Classic McEliece: Khi giả định về tính giả ngẫu nhiên không còn đứng vững

Classic McEliece là một trong những hệ mật mã khóa công khai lâu đời nhất được thiết kế để kháng lại máy tính lượng tử. Được Robert McEliece đề xuất từ năm 1978, hệ mật McEliece dựa trên mã sửa sai vẫn trụ vững trước nỗ lực tấn công thám mã trong gần 50 năm qua. Khi làn sóng mật mã hậu lượng tử (PQC) bùng nổ, Classic McEliece tiếp tục khẳng định vị thế là một trong những ứng viên kiên cố nhất nhờ khả năng kháng lại cả máy tính truyền thống lẫn máy tính lượng tử. Tuy nhiên, mới đây vào ngày 10/08/2026, bài báo khoa học đăng tải trên trang tiền ấn phẩm của Hiệp hội mật mã học thế giới IACR ePrint 2026/1630 [1] với tiêu đề “A New Classic McEliece Distinguisher Undercuts Generic Decoding. It Is Not a Break” đã thu hút sự chú ý lớn khi chỉ ra một lỗ hổng trong giả định nền tảng gắn liền với Classic McEliece – về tính giả ngẫu nhiên của khóa công khai – không còn đúng về mặt lý thuyết đã biết trước đó.

McEliece – tượng đài kháng lượng tử với khóa công khai khổng lồ: Hệ mật McEliece sử dụng mã Goppa, một họ mã sửa sai có cấu trúc đại số ẩn để tạo ra cặp khóa. Khóa công khai là một ma trận sinh đã được “ngụy trang”, còn khóa bí mật chứa thông tin để giải mã hiệu quả. Điểm mạnh của McEliece là độ an toàn của nó dựa trên bài toán giải mã hội chứng tổng quát (syndrome decoding) cho mã tuyến tính ngẫu nhiên, một bài toán được tin là khó ngay cả với máy tính lượng tử.

Dù vậy, Classic McEliece chưa bao giờ được Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (National Institute of Standards and Technology – NIST) chọn làm tiêu chuẩn cho cơ chế đóng gói khóa (KEM). Trong tiến trình chuẩn hóa mật mã hậu lượng tử, NIST đã chọn ML-KEM (Kyber) và gần đây là HQC-KEM, bởi lý do đưa ra là McEliece sở hữu khóa công khai rất lớn và hiệu năng sinh khóa kém. Kích thước khóa công khai có thể lên tới hơn 1 MB là trở ngại lớn cho các ứng dụng thực tế. Tuy vậy, về mặt lý thuyết, McEliece vẫn được coi là một trong những ứng viên an toàn bậc nhất.

Bản chất của phát hiện mới: Bộ phân biệt cấu trúc thời gian tựa đa thức

Để hiểu đúng bản chất của nghiên cứu, cần phân biệt rõ giữa bài toán giải mã và bài toán phân biệt cấu trúc:

– Mã ngẫu nhiên và Mã Goppa: Khóa công khai của Classic McEliece là một ma trận sinh đại diện cho một mã Goppa nhị phân đã bị ẩn giấu qua các phép biến đổi.

– Bộ phân biệt cấu trúc: Là một thuật toán toán học nhằm trả lời câu hỏi: “Liệu ma trận khóa công khai này có chứa cấu trúc toán học ẩn của mã Goppa hay nó chỉ là một ma trận mã tuyến tính ngẫu nhiên?”

Điểm mấu chốt trong kết quả mới công bố này: lần đầu tiên, người ta tìm ra một phương pháp có thể chứng minh được trong thời gian tựa đa thức để phân biệt khóa công khai của Classic McEliece với một mã tuyến tính thực sự ngẫu nhiên. Nghiên cứu mới đã tìm ra phương pháp thời gian tựa đa thức  cho phép phát hiện cấu trúc ẩn của mã Goppa trong ma trận công khai. Nói một cách đơn giản, bộ phân biệt cấu trúc này giống như một “máy dò” có thể nhìn vào ma trận sinh công khai và trả lời câu hỏi: “Ma trận này có phải được tạo ra từ thuật toán McEliece hay chỉ là một mã ngẫu nhiên?”. Nó không khôi phục khóa bí mật, cũng không giải mã được bất kỳ bản mã nào. Phát hiện này thuần túy mang ý nghĩa lý thuyết: nó cho thấy khóa công khai của McEliece mang trong mình một cấu trúc toán học có thể nhận diện được, chứ không hoàn toàn “vô danh” như người ta vẫn ngầm tin.

Giáo sư Bill Buchanan, tại Đại học Edinburgh Napier, nhận định trên LinkedIn [3]: “Với khả năng phân biệt cấu trúc, bài báo chỉ ra rằng mã công khai có thể phân biệt được với mã ngẫu nhiên… Đây là điều mà Classic McEliece chưa bao giờ thực sự tuyên bố là đúng, và cũng chưa từng nằm trong các chứng minh an toàn hình thức cho hệ mật này.”

Điểm gây chú ý nhất là mức giảm chi phí ước tính cho việc thực thi bộ phân biệt. Đối với các bộ tham số tiêu chuẩn hiện tại của Classic McEliece, chi phí tính toán để phân biệt ma trận khóa công khai với ma trận ngẫu nhiên đã giảm mạnh. Chi phí của bộ phân biệt cấu trúc tốt nhất trước đây rơi vào khoảng   đến  phép tính, thì với phương pháp mới, con số này tụt xuống chỉ còn khoảng  đến . Đây là mức giảm khổng lồ xét về mặt lý thuyết (hàng trăm bậc độ lớn), nhưng (~2 × ) phép tính vẫn là một con số nằm ngoài tầm với của mọi siêu máy tính hiện tại và tương lai gần. Do đó, không một kẻ tấn công thực tế nào có thể vận hành bộ phân biệt này. Tuy nhiên, sự suy giảm này đã chạm tới ngưỡng an toàn mức 1 ( ) theo tiêu chí NIST.

Tại sao không phải là một tấn công phá vỡ Classic McEliece?

Mặc dù con số tạo ra cảm giác lo ngại về mặt lý thuyết, cộng đồng mật mã học cần nhìn nhận chính xác các giới hạn của nghiên cứu này. Bộ phân biệt cấu trúc chỉ làm nhiệm vụ xác nhận sự tồn tại của cấu trúc toán học ẩn trong ma trận công khai. Thuật toán này không cung cấp bất kỳ công cụ nào để khôi phục khóa bí mật, cũng như không thể giải mã bất kỳ bản mã nào để lấy lại thông điệp ban đầu. Marin Ivezic, tác giả bài phân tích trên postquantum.com [2], nhấn mạnh: “Đây không phải là một tấn công phá vỡ.” Cùng quan điểm, GS. Buchanan viết: “Thật may mắn, tấn công hiện không khả thi, sẽ đắt đỏ khó tin, và bản mã sẽ không thể bị giải mã. Nó cũng không làm lộ bất kỳ phần nào của khóa.”

Vì sao điều này vẫn đáng quan tâm?

Dù không trực tiếp đe dọa tính an toàn của các bản mã, kết quả trên vẫn là một bước lùi lý thuyết đối với McEliece. Độ an toàn của Classic McEliece dựa trên bài toán giải mã hội chứng tổng quát (Syndrome Decoding Problem – SDP) một bài toán đã được chứng minh là NP-khó. Tấn công phân biệt cấu trúc mới hoàn toàn không làm giảm độ khó hay cải thiện tốc độ giải bài toán SDP. Tuy nhiên, tính không thể phân biệt cấu trúc chưa từng được tuyên bố hay bao hàm trong các chứng minh an toàn hình thức của Classic McEliece. Hệ mật này hoạt động và đảm bảo tính an toàn dựa trên độ khó của việc giải mã mã ngẫu nhiên, bất kể ma trận đó có bị phân biệt hay không.

Trước đây, cộng đồng mật mã thường ngầm giả định rằng không tồn tại thuật toán hiệu quả để phân biệt khóa công khai McEliece với mã ngẫu nhiên. Giả định này tuy không phải là trụ cột trong các chứng minh an toàn IND-CCA2 hình thức mà nhóm thiết kế đệ trình lên NIST, nhưng nó là một “chỉ báo” cho thấy hệ mật không có điểm yếu cấu trúc tiềm ẩn. Việc giả định đó sụp đổ đồng nghĩa với việc người ta đã tìm thấy một phương pháp có thể lần ra trong cấu trúc đại số của mã Goppa.

Về mặt nghiên cứu, công trình này tiếp tục khẳng định một nguyên tắc của mật mã học: những cấu trúc toán học ẩn giấu tưởng như không thể phát hiện vẫn có thể lộ diện khi có công cụ phân tích mới. Nó cũng đặt ra câu hỏi liệu từ bộ phân biệt này, trong tương lai xa, có thể mở đường cho các kỹ thuật khôi phục khóa hay không. Hiện tại chưa có bằng chứng nào cho thấy điều đó khả thi. Đối với những ai đã chọn Classic McEliece, đặc biệt trong khung tiêu chuẩn ISO/IEC 18033-2 [4], thông tin này nhấn mạnh tầm quan trọng của việc theo dõi sát sao các tiến bộ phân tích mật mã, nhưng không đòi hỏi phải thay đổi hệ thống ngay lập tức.

Kết luận

Nghiên cứu mới này về bộ phân biệt thời gian tựa đa thức là một đóng góp quan trọng cho lý thuyết mật mã dựa trên mã sửa sai. Kết quả này buộc các nhà toán học và nghiên cứu mật mã phải đánh giá lại lề an toàn và có thể tính toán điều chỉnh nhẹ các bộ tham số của mã Goppa trong tương lai. Đối với các tổ chức và chuyên gia an toàn thông tin, thông điệp rút ra: Classic McEliece chưa bị phá vỡ. Dữ liệu được mã hóa bằng hệ mật này vẫn an toàn trước nguy cơ giải mã hay dò khóa, kể cả dưới sự đe dọa của máy tính lượng tử trong tương lai. Tuy nhiên, đây là lần đầu tiên một giả định an toàn thầm lặng đi cùng hệ mật gần 50 năm tuổi bị bác bỏ về mặt lý thuyết. Điều này nhắc nhở chúng ta rằng ngay cả những thiết kế được kiểm chứng kỹ lưỡng cũng cần được liên tục soi xét. Trong cuộc đua giữa người xây dựng và người phá mã hậu lượng tử, không có pháo đài nào là bất khả xâm phạm.