Shortest Vector Problem (SVP) là một trong những bài toán quan trọng nhất trong lý thuyết lattice, nó yêu cầu tìm kiếm vector ngắn nhất trong một lattice cho trước. Cụ thể hơn, cho một lattice L được tạo bởi một tập các vector linearly independent, SVP yêu cầu tìm một vector v thuộc L sao cho độ dài của v là nhỏ nhất có thể.
SVP là một bài toán khó tính, tức là không có thuật toán hiệu quả để giải quyết nó trong thời gian đa thức với độ phức tạp vượt quá một hằng số nhất định. Bài toán SVP là cơ sở cho nhiều thuật toán mã hóa và chữ ký dựa trên lattice, vì nó đảm bảo tính an toàn của hệ thống mã hóa và chữ ký. Nếu có một thuật toán hiệu quả để giải quyết bài toán SVP, thì nó sẽ phá vỡ hầu hết các hệ thống mã hóa và chữ ký lattice-based. Hiện nay, các thuật toán tiêu biểu để giải quyết SVP bao gồm thuật toán Babai, thuật toán Kannan và thuật toán LLL (Lenstra-Lenstra-Lovász). Tuy nhiên, các thuật toán này đều chỉ áp dụng cho các lattice có kích thước nhỏ, trong khi với các lattice lớn, SVP vẫn là một bài toán khó.
Các thuật toán giải bài toán SVP
Hiện nay, có nhiều thuật toán được đề xuất để giải bài toán SVP trong lattice, tuy nhiên, đa phần chỉ áp dụng được cho các lattice có kích thước nhỏ. Các thuật toán tiêu biểu như sau:
- Thuật toán Babai: Đây là thuật toán đơn giản và trực tiếp để giải quyết SVP, nó dựa trên tính chất của projection để tìm kiếm vector ngắn nhất. Tuy nhiên, độ phức tạp của thuật toán là hàm bậc ba của số chiều và chi phí tính toán tăng nhanh khi số chiều tăng.
- Thuật toán Kannan: Thuật toán này dựa trên các tính chất của hình ảnh convex của lattice, tuy nhiên, độ phức tạp của nó cũng là hàm bậc ba của số chiều.
- Thuật toán LLL (Lenstra-Lenstra-Lovász): Đây là một thuật toán quan trọng trong lý thuyết lattice, nó giúp thu gọn các vector của lattice để có thể tìm kiếm vector ngắn nhất một cách hiệu quả hơn. Tuy nhiên, độ phức tạp của thuật toán LLL cũng là hàm bậc ba của số chiều.
- Thuật toán BKZ (Block Korkin-Zolotarev): Đây là một thuật toán hiệu quả hơn so với LLL để giải quyết SVP, độ phức tạp của nó là hàm exponent của số chiều, cho phép giải quyết được các bài toán lớn hơn.
- Thuật toán Schnorr-Euchner: Thuật toán này kết hợp phương pháp Babai và thuật toán dò tìm để tìm kiếm vector ngắn nhất.
- Thuật toán GaussSieve: Đây là thuật toán dựa trên phương pháp lattice sieving, nó có thể giải quyết SVP cho các lattice kích thước lớn hơn so với LLL và BKZ, nhưng độ phức tạp của nó vẫn là hàm exponent của số chiều.
- Thuật toán Pohst-Rem: Thuật toán này sử dụng phương pháp phân tách để giải quyết SVP cho các lattice có kích thước nhỏ, nhưng độ phức tạp tính toán của nó là hàm bậc ba của số chiều.
Tóm lại, SVP là một bài toán khó trong lý thuyết lattice và hiện chưa có thuật toán nào có thể giải quyết nhanh chóng cho các lattice lớn. Tuy nhiên, các thuật toán như LLL và BKZ vẫn là các giải pháp hiệu quả để giải quyết SVP cho các lattice kích thước nhỏ và vừa.
