Closest Vector Problem (CVP) là bài toán tìm kiếm vector trong một lattice gần nhất với một vector đã cho. Cụ thể hơn, cho một lattice L với basis B = [b1, b2, …, bn] và một vector w không thuộc L, bài toán CVP yêu cầu tìm vector v thuộc L sao cho khoảng cách Euclide giữa v và w là nhỏ nhất. Khoảng cách Euclide giữa hai vector a và b được tính bằng cách lấy căn bậc hai của tổng bình phương của hiệu của các thành phần của chúng.
CVP là một trong những bài toán cơ bản của lý thuyết lattice và là một bài toán quan trọng trong nhiều ứng dụng của lattice-based cryptography, chẳng hạn như mã hóa và chữ ký lattice. Nó cũng có ứng dụng trong các lĩnh vực khác như định tuyến trong mạng lưới và xử lý ảnh.
Tuy nhiên, CVP cũng là một bài toán NP-khó, có nghĩa là không có thuật toán hiệu quả đã biết để giải quyết nó trong thời gian đa thức. Do đó, trong thực tế, các thuật toán giải quyết CVP thường chỉ được áp dụng cho các lattice có kích thước nhỏ hoặc có cấu trúc đặc biệt, trong khi các lattice lớn và tổng quát hơn thường không thể được giải quyết bằng cách chính xác.
Các thuật toán giải Closest Vector Problem (CVP)
Hiện tại, không có thuật toán chính xác và hiệu quả để giải quyết bài toán CVP trên mọi lattice. Tuy nhiên, có nhiều thuật toán xấp xỉ được đề xuất để giải quyết bài toán CVP, tùy thuộc vào tính chất của lattice.
- Thuật toán Babai’s algorithm: Đây là thuật toán đầu tiên được đề xuất để giải quyết bài toán CVP. Nó dựa trên việc tìm kiếm một linear combination của các basis vector sao cho khoảng cách giữa vector thu được và vector ban đầu là nhỏ nhất. Tuy nhiên, độ phức tạp của thuật toán là lũy thừa của chiều d của lattice, vì vậy nó không được sử dụng trong thực tế.
- Thuật toán Schnorr-Euchner: Đây là một thuật toán xấp xỉ được sử dụng để giải quyết bài toán CVP trên các lattice có cấu trúc đặc biệt. Nó dựa trên việc tìm kiếm tất cả các vector có thể và so sánh khoảng cách của chúng với vector ban đầu. Độ phức tạp của thuật toán là 2^O(d/2), với d là chiều của lattice.
- Thuật toán Kannan’s algorithm: Đây là một trong những thuật toán hiệu quả nhất để giải quyết bài toán CVP trên các lattice tổng quát. Thuật toán sử dụng kỹ thuật dò tìm ngưỡng (threshold finding) để xác định một số ngưỡng phân chia các vector thành hai nhóm, một nhóm gần với vector ban đầu hơn và một nhóm khác gần hơn với vector gốc. Sau đó, thuật toán tiếp tục tìm kiếm trên nhóm gần với vector ban đầu. Độ phức tạp của thuật toán là 2^O(dlogd).
- Thuật toán LLL: Thuật toán LLL (Lenstra–Lenstra–Lovász) là một thuật toán quan trọng trong lý thuyết lattice. Nó không được thiết kế để giải quyết bài toán CVP trực tiếp, nhưng nó có thể được sử dụng để tìm kiếm một basis vector gần nhất với vector ban đầu. Độ phức tạp của thuật toán LLL là 2^O(d^2).
- Brute force: Cách giải đơn giản nhất là liệt kê tất cả các vector trong lattice và chọn ra vector gần nhất với vector đích. Tuy nhiên, độ phức tạp thời gian của phương pháp này là $O(2^n)$ với $n$ là số chiều của lattice nên chỉ áp dụng được với các lattice có số chiều nhỏ.
- Schnorr’s algorithm: Đây là một thuật toán probabilistic để giải bài toán CVP. Thuật toán này sử dụng một phương pháp tương tự như Babai’s algorithm, nhưng có thêm yếu tố ngẫu nhiên. Độ phức tạp thời gian của thuật toán Schnorr’s là $O(n^2 \log q)$ với $n$ là số chiều của lattice và $q$ là một số nguyên tố lớn đủ lớn để đảm bảo an toàn.
- Ajtai’s algorithm: Đây là một thuật toán probabilistic khác để giải bài toán CVP. Thuật toán này sử dụng một phương pháp gọi là “perturbation”, tức là thêm một vector ngẫu nhiên vào lattice để tạo ra một lattice mới. Độ phức tạp thời gian của Ajtai’s algorithm là $O(n^2)$ với $n$ là số chiều của lattice.
