1.2. Các bài toán khó¶
Bài toán 1. (Bài toán nhóm con ẩn, Hidden Group Problem - HGP).
Cho một nhóm \(G\) và một hàm \(f\) trên \(G\) là hằng số và phân biệt trên các coset của nhóm con \(H\) nào đó chưa biết của \(G\). Hãy tìm một tập các phần tử sinh của \(H\).
Bài toán 2. (Bài toán vector ngắn nhất, Shortest Vector Problem - SVP)
Cho một cơ sở tùy ý \(\bm{V}\) của lattice \(\mathcal{L}\). Hãy tìm một vector \(\bm{x} \in \mathcal{L}\) khác không với \(\lVert \bm{x} \rVert \leqslant \gamma(n) \cdot \lambda_1(\mathcal{L})\).
Bài toán 3. (Bài toán Learning With Error, LWE Problem)
Cho \(n, m, q > 0\) là các số nguyên và \(\chi\) là một phân bố lỗi trên \(\mathbb{Z}\). Với bí mật \(\bm{s} \xleftarrow{\$} \mathbb{Z}_q^n\), định nghĩa \(\mathcal{D}_{\bm{s}, \chi}\) là phân bố lấy các mẫu \(\bm{a} \xleftarrow{\$} \mathbb{Z}_q^n\) và \(e \xleftarrow{\chi} \mathbb{Z}\). Kết quả trả về \((\bm{a}, \langle \bm{a}, \bm{s} \rangle + e \bmod q) \in \mathbb{Z}_q^n \times \mathbb{Z}_q\).
Với \(n, q \geqslant 2\) và \(m\) mẫu độc lập từ phân bố \(\mathcal{D}_{\bm{s}, \chi}\), bài toán LWE tìm kiếm là tìm \(\bm{s}\) (search LWE problem).
Với \(n, q \geqslant 2\) và \(m\) mẫu độc lập \((\bm{a}_i, b_i)\), bài toán LWE quyết định (decisional LWE problem) là phân biệt với \(i = 1, \ldots, m\) thì \((\bm{a}_i, b_i)\) thuộc \(\mathbb{Z}_q^n \times \mathbb{Z}_q\) hay thuộc \(\mathcal{D}_{\bm{s}, \chi}\). Nói cách khác là được lấy mẫu ngẫu nhiên theo \(\mathbb{Z}_q^n \times \mathbb{Z}_q\) hay theo phân bố \(\mathcal{D}\).
Thông thường chúng ta coi vector \(\bm{s}\) là secret và \(e\) là lỗi (error) của LWE.
Chúng ta nói rằng bài toán LWE quyết định \(\text{LWE}_{n, m, q, \chi}\) là \((t, \varepsilon)\)-hard nếu đối với bất kì thuật toán \(\mathcal{A}\) nào chạy trong thời gian \(t\), nó đảm bảo rằng:
Bài toán 4. (Bài toán Ring-LWE, R-LWE)
Cho \(n, q > 0\) là các số nguyên và \(\chi\) là phân bố trên \(\mathcal{R}\). Với \(s \xleftarrow{\$} \mathcal{R}\), định nghĩa \(\mathcal{D}_{s, \chi}\) là phân bố lấy các mẫu \(a \xleftarrow{\$} \mathcal{R}_q\) và \(e \xleftarrow{\chi} \mathcal{R}\). Kết quả trả về \((a, a s + e) \in \mathcal{R}_q \times \mathcal{R}_q\).
Tương tự:
Bài toán R-LWE tìm kiếm (search ring-LWE problem) là tìm \(s\).
Bài toán R-LWE quyết định (decisional ring-LWE problem) là phân biệt \((a_i, b_i) \xleftarrow{\$} \mathcal{R}_q \times \mathcal{R}_q\) hay \((a_i, b_i) \gets \mathcal{D}_{s, \chi}\).
1.2.1. Short vectors trong lattice¶
Các bài toán liên quan tới lattice mà chúng ta cần quan tâm để xây dựng các thuật toán mã hóa lattice-based.
Shortest Vector Problem (hay SVP): Tìm vector khác không có độ dài ngắn nhất trong lattice \(\mathcal{L}\), nghĩa là tìm \(\bm{v} \in \mathcal{L}\) sao cho \(\lVert \bm{v} \rVert\) nhỏ nhất;
Closest Vector Problem (hay CVP): Cho trước vector \(\bm{w} \in \mathbb{R}^n\) mà không nằm trong \(\mathcal{L}\), tìm \(\bm{v} \in \mathcal{L}\) gần với \(\bm{w}\) nhất, nghĩa là cực tiểu hóa \(\lVert \bm{w} - \bm{v} \rVert\).
1.2.2. Thuật toán Babai¶
Thuật toán này giúp tìm một cơ sở "đủ tốt" để giải apprCVP.
Định lý 1.2 (Thuật toán Babai tìm vector gần nhất)
Gọi \(\mathcal{L} \subset \mathbb{R}^n\) là lattice với cơ sở là \(\bm{v}_1\), \(\bm{v}_2\), ..., \(\bm{v}_n\) và gọi \(\bm{w} \in \mathbb{R}^n\) là vector bất kỳ.
Nếu các vector trong cơ sở trực giao nhau thì thuật toán Babai sẽ giải được CVP.
Nếu các vector trong cơ sở gần như trực giao thì thuật toán Babai sẽ giải được apprCVP.
Ngược lại, nếu các vector trong cơ sở không trực giao (nhiều) thì kết quả thuật toán trả về sẽ xa hơn vector gần với \(\bm{w}\).
Thuật toán 1.1 (Thuật toán điểm gần nhất của Babai)
Biểu diễn \(\bm{w} = t_1 \bm{v}_1 + t_2 \bm{v}_2 + \ldots + t_n \bm{v}_n\) với \(t_1, \ldots, t_n \in \mathbb{R}\).
Đặt \(a_i = \lfloor t_i \rceil\) với \(i = 1, \ldots, n\).
Trả về vector \(\bm{v} = a_1 \bm{v}_1 + a_2 \bm{v}_2 + \ldots + a_n \bm{v}_n\).
Có thể thấy thuật toán Babai làm tròn các hệ số để trả về một vector lattice gần với \(\bm{w}\).