Thuật toán Babai’s algorithm là một thuật toán để giải bài toán Closest Vector Problem (CVP) trong lattice-based cryptography. Ý tưởng chính của thuật toán là sử dụng phép biến đổi ma trận để giảm độ dài của vector cần tìm.
Cụ thể, giả sử có một lattice L được xác định bởi một ma trận cơ bản A. Và giả sử vị trí của vector cần tìm (v) là không rõ nhưng nó nằm gần một vector khác trong lattice, gọi là u. Để tìm vector v, thuật toán Babai’s sẽ biến đổi ma trận A thành dạng Hermite H bằng cách sử dụng các phép biến đổi hàng và cột, rồi tính toán vector u’ tương ứng với u trong không gian mới được tạo ra bởi dạng Hermite H.
Cụ thể, các bước của thuật toán Babai’s như sau:
- Tính toán ma trận dạng Hermite H của ma trận cơ bản A của lattice L.
- Chuyển đổi vector cần tìm (v) và vector gần nó nhất (u) thành các vector tương ứng v’ và u’ trong không gian mới được tạo ra bởi dạng Hermite H.
- Sử dụng một thuật toán tìm kiếm đơn giản, ví dụ như thuật toán brute-force, để tìm kiếm vector ngắn nhất trong tập hợp các vector cột của ma trận H trừ vector u’.
- Tính toán vector v tương ứng với vector ngắn nhất tìm được ở bước 3 bằng cách lấy tổng trọng số của các vector cột tương ứng với các phần tử trong vector ngắn nhất đó.
Thuật toán Babai’s cho phép giải quyết bài toán CVP với độ phức tạp thời gian O(n^3) với n là kích thước của ma trận cơ bản A của lattice L. Tuy nhiên, nó không hiệu quả khi sử dụng cho các lattice lớn và có thể được cải tiến bằng cách sử dụng các thuật toán tìm kiếm vector ngắn nhất khác.
Ví dụ về thuật toán Babai’s algorithm
Giả sử ta có một lattice trong không gian hai chiều được sinh bởi hai vector cơ sở sau:
B = {(3, -1), (5, -1)}Ta muốn tìm closest vector với tọa độ (9, 2) trong lattice B.
Để áp dụng thuật toán Babai’s, ta cần chuyển đổi lattice B thành dạng Hermite. Ta có thể thực hiện như sau:
Bước 1: Đặt vector thứ nhất làm pivot vector. Ta đổi chỗ hai vector trong lattice B để vector (3, -1) được đặt đầu tiên. Khi đó, ma trận của lattice B trở thành:
[ 3 5 ] [-1 -1 ]
Bước 2: Sử dụng phép biến đổi hàng để đưa các phần tử không nằm trong cột pivot về 0. Ta trừ 1 lần vector thứ 2 cho 1 lần vector thứ nhất nhân với 5/3. Kết quả là:
[ 3 5 ] [ 0 2 ]
Bước 3: Tiếp tục sử dụng phép biến đổi hàng để đưa các phần tử không nằm trong cột pivot về 0. Ta trừ 2 lần vector thứ 2 cho 3 lần vector thứ nhất. Kết quả là:
[ 3 5 ] [ 0 2 ]
Khi đó, lattice B đã được chuyển đổi thành dạng Hermite. Ma trận Hermite tương ứng với lattice B là:
[ 3 5 ] [ 0 2 ]
Bây giờ, ta áp dụng thuật toán Babai’s để tìm closest vector của (9, 2) trong lattice B. Ta tính toán:
c2 = round(2/2) = 1 c1 = round((5*1 + 3)/3) = 2
Khi đó, closest vector với tọa độ (9, 2) trong lattice B là:
(2*3 + 1*5, 2*-1 + 1*-1) = (11, -3)
