Thuật toán LLL (Lenstra-Lenstra-Lovász) là một trong những thuật toán phổ biến nhất để giải bài toán tìm vector ngắn nhất đầu tiên (SVP) trong hệ thống mã hóa dựa trên lưới (lattice-based cryptography). Thuật toán này được đặt tên theo tên ba nhà toán học là A.K. Lenstra, H.W. Lenstra, và L. Lovász, người đã đề xuất nó vào năm 1982.
Thuật toán LLL hoạt động trên một ma trận cơ sở của lưới và có hai bước chính:
Bước 1: Thuật toán thực hiện một số phép biến đổi trên ma trận cơ sở của lưới để đưa nó về dạng “thuận tiện” để tính toán. Trong quá trình này, thuật toán thực hiện một số phép biến đổi trên các hàng của ma trận cơ sở để đưa các giá trị của ma trận Gram về gần đường chéo chính. Việc làm này giúp tăng hiệu quả tính toán của thuật toán.
Bước 2: Sau khi ma trận cơ sở của lưới đã được đưa về dạng thuận tiện, thuật toán tiến hành tìm kiếm vector ngắn nhất trong lưới. Việc tìm kiếm này được thực hiện bằng cách duyệt qua từng cột của ma trận cơ sở và thay đổi các phần tử của cột đó để giảm giá trị của vector ngắn nhất được tìm thấy trước đó. Quá trình tìm kiếm được tiếp tục cho đến khi không thể tìm được vector ngắn hơn nữa.
Thuật toán LLL có thể giải bài toán SVP nhanh hơn so với thuật toán Kannan, nhưng vẫn có thể bị đánh bại bởi các thuật toán mới hơn như thuật toán BKZ (Block Korkin-Zolotarev). Tuy nhiên, thuật toán LLL vẫn là một công cụ quan trọng trong các hệ thống mã hóa dựa trên lưới.
Ví dụ về Thuật toán LLL (Lenstra-Lenstra-Lovász)
Để minh họa cho thuật toán LLL, ta xét một ví dụ đơn giản về bài toán SVP trên lưới hai chiều. Giả sử ta có một lưới với hai vector cơ sở:
B = [3 1]
[1 2]Ta muốn tìm vector ngắn nhất trong lưới này. Để làm được điều đó, ta bắt đầu bằng việc áp dụng bước 1 của thuật toán LLL, tức là đưa ma trận cơ sở về dạng “thuận tiện”. Để đơn giản, ta chỉ xét bước này trên từng hàng của ma trận cơ sở:
Bước 1: Thực hiện phép biến đổi đầu tiên
b1' = b1 b2' = b2 - mu21 * b1'
với mu21 là hệ số được tính như sau:
mu21 = round((b2 . b1) / (b1 . b1))
Trong trường hợp này, ta có:
mu21 = round((1*3 + 2*1) / (3*3 + 1*1)) = round(5/10) = 1
Do đó, ta thực hiện phép biến đổi trên b2:
b1' = [3 1] b2' = [1 2] - 1 * [3 1] = [-2 1]
Bước 1: Thực hiện phép biến đổi thứ hai
b1'' = b1' b2'' = b2' - mu21 * b1''
với mu21 được tính bằng công thức như trên. Trong trường hợp này, ta có:
mu21 = round((-2*3 + 1*1) / (3*3 + 1*1)) = round(-5/10) = -1
Do đó, ta thực hiện phép biến đổi trên b2':
b1'' = [3 1] b2'' = [-2 1] - (-1) * [3 1] = [-5 -1]
Sau khi thực hiện bước 1, ma trận cơ sở của lưới được đưa về dạng:
B' = [3 1]
[-5 -1]Bước 2: Tìm vector ngắn nhất trong lưới. Ta duyệt qua từng cột của ma trận cơ sở và tìm kiếm các phần tử có thể thay đổi để giảm giá trị của vector ngắn nhất. Để đơn giản, ta chỉ xét phép biến đổi trên cột đầu tiên.
Bước 2.1: Tìm phần tử có thể thay đổi trên cột đầu tiên. Ta thực hiện tính toán để tìm phần tử có thể thay đổi trên cột đầu tiên, ta tính toán giá trị delta như sau:
delta = round((-5*3 + (-1)*1) / (3*3 + 1*1)) = round(-16/10) = -2
Bước 2.2: Thực hiện phép biến đổi trên cột đầu tiên.
b1''' = b1' b2''' = b2'' + delta * b1'''
Ta thực hiện phép biến đổi trên b2'':
b1''' = [3 1] b2''' = [-5 -1] + (-2) * [3 1] = [-11 -3]
Bước 2.3: Kiểm tra xem vector mới có ngắn hơn không. Ta tính độ dài của vector b2''':
||b2'''||^2 = (-11)^2 + (-3)^2 = 130
So sánh với độ dài của vector b2'':
||b2''||^2 = (-5)^2 + (-1)^2 = 26
Vì ||b2'''||^2 lớn hơn ||b2''||^2, nên ta bỏ qua phép biến đổi trên cột đầu tiên.
Bước 3: Kiểm tra điều kiện kết thúc. Vì ma trận cơ sở đã ở dạng thuận tiện và không có phép biến đổi nào được thực hiện trong bước 2, nên ta kết luận rằng vector ngắn nhất trong lưới là b2''. Độ dài của nó là:
||b2''||^2 = (-5)^2 + (-1)^2 = 26
Vì độ dài này là ngắn nhất trong lưới, nên đây chính là kết quả của bài toán SVP trên lưới hai chiều với ma trận cơ sở B.
