THUẬT TOÁN LLL GỐC

Trong thời đại công nghệ số đang bùng nổ hiện nay, độ an toàn của các công nghệ phụ thuộc nhiều vào mật mã. Khi gửi tin nhắn riêng tư hoặc thanh toán hóa đơn trực tuyến, người dùng đang dựa vào các thuật toán được thiết kế để giữ bí mật dữ liệu của mình. Một số tác nhân muốn khám phá những bí mật đó, vì vậy các nhà nghiên cứu phải thường xuyên kiểm tra sức mạnh của những hệ thống này để đảm bảo chúng sẽ không bị xâm phạm.

Một công cụ quan trọng được sử dụng là [3], được đặt theo tên của các nhà nghiên cứu đã công bố nó vào năm 1982 - Arjen Lenstra, Hendrik Lenstra Jr. và László Lovász. Thuật toán LLL, cùng với nhiều biến thể trước đó, có thể phá vỡ các lược đồ mật mã trong một số trường hợp. Việc nghiên cứu cách thức hoạt động của chúng giúp các nhà nghiên cứu thiết kế các hệ thống khó bị tấn công hơn. Ứng dụng của thuật toán còn vượt ra ngoài lĩnh vực mật mã, nó còn là một công cụ hữu ích trong các lĩnh vực toán học tiên tiến như lý thuyết số tính toán.

Các thuật toán kiểu LLL hoạt động trong thế giới của các lưới, đó là tập hợp vô hạn các điểm cách đều nhau. Người ta có thể hình dung điều này giống như việc lát sàn nhà. Có thể lát lên sàn nhà bằng những viên gạch hình vuông và các góc của những viên gạch đó sẽ tạo thành một lưới. Ngoài ra có thể chọn một hình dạng ô xếp khác chẳng hạn như lát bằng những viên gạch hình bình hành dài để tạo một lưới khác.

Một lưới có thể được mô tả bằng cách sử dụng “cơ sở” của nó. Đây là một tập hợp các vectơ (thực chất là danh sách các số) có thể kết hợp theo nhiều cách khác nhau để có được mọi điểm trong lưới. Hãy tưởng tượng một lưới có cơ sở gồm hai vectơ: [3, 2] và [1, 4]. Lưới chỉ bao gồm tất cả các điểm có thể đạt được bằng cách cộng và trừ các bản sao của các vectơ đó.

Cặp vectơ đó không phải là cơ sở duy nhất của mạng. Mọi lưới có ít nhất hai chiều đều có thể có vô số cơ sở. Nhưng không phải tất cả các cơ sở đều được tạo ra như nhau. Một cơ sở có các vectơ ngắn hơn và gần góc vuông với nhau thường hữu ích hơn trong việc giải một số bài toán, vì vậy các nhà nghiên cứu gọi những cơ sở đó là “tốt”, ví dụ về điều này là cặp vectơ màu xanh lam trong Hình 1. Các cơ sở bao gồm các vectơ dài hơn và ít trực giao hơn như các vectơ màu đỏ (Hình 1), các vectơ này có thể bị coi là “xấu”.

Hình 1. Ví dụ về cơ sở của lưới

Công việc của thuật toán LLL là cung cấp cho nó hoặc những người anh em của nó một cơ sở của lưới đa chiều từ đó sẽ tạo ra một lưới tốt hơn. Quá trình này được gọi là rút gọn cơ sở lưới.

Trong một số trường hợp, nhiệm vụ phá vỡ một hệ thống mật mã có thể được biến đổi thành một bài toán khác như tìm một vectơ tương đối ngắn trong một lưới. Đôi khi, vectơ đó có thể được lấy ra từ cơ sở rút gọn được tạo bởi thuật toán kiểu LLL. Chiến lược này đã giúp các nhà nghiên cứu phá vỡ các hệ thống mà nhìn bề ngoài dường như ít liên quan đến các lưới.

THUẬT TOÁN ĐƯỢC NÂNG CẤP

Về mặt lý thuyết, thuật toán LLL gốc chạy khá nhanh: Thời gian chạy không tăng theo hàm mũ với kích thước của đầu vào (kích thước của lưới và kích thước của các số trong các vectơ cơ sở tính bằng bit) nhưng nó tăng lên như một hàm đa thức. Nhà mật mã học Léo Ducas tại Viện nghiên cứu quốc gia CWI (Hà Lan) nhận định: “Nếu bạn thực sự muốn làm điều đó, thời gian đa thức không phải lúc nào cũng khả thi”. Về mặt thực hành, điều này có nghĩa là thuật toán LLL gốc không thể xử lý các đầu vào quá lớn trong khi các nhà toán học và mật mã muốn nó có khả năng làm được nhiều hơn thế. Các nhà nghiên cứu đã làm việc để tối ưu hóa các thuật toán kiểu LLL nhằm đáp ứng đầu vào lớn hơn và đạt được hiệu suất tốt hơn. Tuy nhiên, một số nhiệm vụ vẫn nằm ngoài tầm với.

Trong nhiều năm, các nhà nghiên cứu đã mài giũa các biến thể của LLL để làm cho phương pháp này trở nên thực tế hơn nhưng chỉ dừng lại ở một mức độ nhất định. Mặc dù vậy, gần đây nhất hai nhà nghiên cứu mật mã đến từ Đại học Canifornia San Diego (Mỹ) là Keegan Ryan và Nadia Heninger, đã xây dựng một thuật toán kiểu LLL mới với hiệu suất tăng đáng kể [4]. Kỹ thuật mới này đã giành được giải Bài báo hay nhất tại Hội nghị Crypto 2023, qua đó mở rộng phạm vi các tình huống trong đó các nhà khoa học máy tính và toán học có thể sử dụng các phương pháp tiếp cận kiểu LLL một cách khả thi. Trước khi công bố kết quả tại Hội nghị Crypto 2023, các tác giả cũng đã đăng một bài báo dài 63 trang về công trình nghiên cứu của mình tại của Hiệp hội mật mã quốc tế [5].

Dưới đây là tóm tắt về thuật toán kiểu LLL mới được Keegan Ryan và Nadia Heninger nghiên cứu. Thuật toán rút gọn cơ sở lưới mới với các thông số đảm bảo xấp xỉ tương tự như thuật toán LLL và hiệu suất thực tế vượt xa trạng thái hiện đại nhất. Những kết quả này đạt được bằng cách áp dụng lặp đi lặp lại các kỹ thuật quản lý độ chính xác trong cấu trúc thuật toán đệ quy, từ đó cho thấy tính ổn định của phương pháp này. Các tác giả đã phân tích hành vi tiệm cận của thuật toán và chỉ ra rằng thời gian chạy thực nghiệm là O(n^w (C+n)^{1+ e}) cho các lưới có kích thước n; w ∈ (2,3] là giới hạn chi phí rút gọn kích thước; nhân ma trận và phân tích QR và C là giới hạn log của số điều kiện của cơ sở đầu vào B. Điều này mang lại thời gian chạy là O(n^w (p+n)^{1+ e}) cho độ chính xác p=O(log‖B‖_max) trong các ứng dụng phổ biến. Thuật toán này hoàn toàn thực tế, các tác giả đã kiểm tra bằng thực nghiệm kết quả của mình và đưa ra các điểm chuẩn rộng lớn đối với nhiều lớp lưới mật mã. Điều đó cho thấy rằng thuật toán mới của Keegan Ryan và Nadia Heninger vượt trội hơn đáng kể so với các thuật toán hiện có [4].

Trong bài báo công bố nghiên cứu mới được viết bởi Ryan và người hướng dẫn Nadia Heninger có kết hợp nhiều chiến lược để nâng cao hiệu quả của thuật toán kiểu LLL. Kỹ thuật này sử dụng cấu trúc đệ quy để chia nhiệm vụ thành các phần nhỏ hơn. Mặt khác, thuật toán quản lý cẩn thận độ chính xác của các con số liên quan, tìm sự cân bằng giữa tốc độ và kết quả chính xác. Công trình mới giúp các nhà nghiên cứu có thể rút gọn cơ sở của các lưới có hàng nghìn chiều.

Một công trình trước đây cũng theo cách tiếp cận tương tự: Một bài báo năm 2021 [6] cũng kết hợp lặp và quản lý độ chính xác để thực hiện nhanh công việc trong các lưới lớn, nhưng nó chỉ hoạt động với các loại lưới cụ thể chứ không phải tất cả các lưới quan trọng trong mật mã, thuật toán mới hoạt động tốt trên phạm vi rộng hơn nhiều. Thomas Espitau, nhà nghiên cứu mật mã tại công ty PQShield và nhóm cộng sự đã đưa ra một “bằng chứng về khái niệm” (PoC), kết quả mới cho thấy rằng có thể thực hiện việc rút gọn lưới rất nhanh một cách hợp lý. Kỹ thuật mới đã bắt đầu tỏ ra hữu ích. Aurel Page, một nhà toán học của Viện nghiên cứu Khoa học máy tính và Tự động hóa Quốc gia Pháp (INRIA) cho biết, ông và nhóm của mình đã áp dụng thuật toán thích ứng để thực hiện một số nhiệm vụ lý thuyết số tính toán.

Các thuật toán kiểu LLL cũng có thể đóng một vai trò trong nghiên cứu liên quan đến dựa trên mạng lưới được thiết kế để duy trì an toàn ngay cả trong tương lai với các máy tính lượng tử mạnh mẽ. Chúng không gây ra mối đe dọa cho những hệ thống như vậy, vì việc phá vỡ đòi hỏi phải tìm ra các vectơ ngắn hơn những gì các thuật toán này có thể đạt được. Wessel van Woerden, nhà mật mã học tại Đại học Bordeaux cho biết, những cuộc tấn công tốt nhất mà các nhà nghiên cứu đã biết sử dụng thuật toán kiểu LLL làm “khối xây dựng cơ bản”. Trong các thí nghiệm thực tế để nghiên cứu các cuộc tấn công này, khối xây dựng đó có thể làm chậm mọi thứ. Bằng cách sử dụng công cụ mới, các nhà nghiên cứu có thể mở rộng phạm vi thử nghiệm mà họ có thể chạy trên các thuật toán tấn công, đưa ra một bức tranh rõ ràng hơn về cách chúng thực hiện.