Tôi không thể tìm thấy một biểu thức rõ ràng cho lợi thế này.
Không có một.
Điều này là do nó phù hợp với trạng thái của nghệ thuật lý thuyết phức tạp mà $\mathsf{P} = \mathsf{NP}$, và do đó $\mathsf{Adv}_{n,m,q,\sigma}^{\mathsf{DLWE}}$ là một số đa thức trong các kích thước của các tham số có liên quan.
Nó là Mà còn phù hợp với suy nghĩ về mật mã hiện tại rằng đây không phải là trường hợp và những điều tích cực hơn là đúng, cụ thể là $\mathsf{Adv}^{\mathsf{DLWE}}_{n,m,q,\sigma}$ hầu như được kiểm soát hoàn toàn bởi $n\log q$, và đặc biệt:
- $m$ có thể khá lớn mà không ảnh hưởng đến bảo mật và
- $\sigma$ có thể khá nhỏ (về mặt lý thuyết $\sigma = \Omega(\sqrt{n})$ thường được yêu cầu, mặc dù thực tế $\sigma = O(1) \xấp xỉ 8$ là phổ biến).
Vậy làm thế nào để đánh giá cụ thể lợi thế này? Nói chung bằng cách (cụ thể) đánh giá công nghệ tiên tiến nhất của các cuộc tấn công đã biết.
Để làm được điều này, có hai nguồn lực chính:
``LWE Estimator'' của Albrecth et al. là vô cùng phổ biến. Bạn có thể xem bài báo ban đầu đâyvà mô-đun hiền triết (cập nhật hơn) đây.
Các đề xuất cụ thể hiện có của các nguyên thủy dựa trên mạng tinh thể. Ví dụ: những người lọt vào vòng chung kết của NIST PQC là Kyber, Sabre và NTRUPrime đều bao gồm phân tích (cụ thể) chứng minh cho các lựa chọn tham số của họ. Đối với nguyên thủy nặng hơn, Tiêu chuẩn mã hóa đồng hình chứa các bảng tham số được đề xuất, cũng như tóm tắt các cuộc tấn công hướng dẫn việc xây dựng các bảng này.
Đó là tất cả những gì đang được nói ...
Có làm giảm $q$ và ngày càng tăng $\sigma$ ngụ ý lợi thế nhỏ hơn (và do đó bảo mật tốt hơn?)
Tất cả những thứ khác đều bình đẳng, câu trả lời là có.
Đưa ra một ví dụ LWE $(\mathbf{A}, \vec b)$, người ta có thể chuyển đổi mô đun từ $q\mapsto q'$ (vì $q' < q$, phân tích sẽ sạch hơn nếu $q' \mid q$ Tuy nhiên).
Điều này đại khái ánh xạ độ lệch chuẩn của lỗi từ $\sigma \mapsto \frac{q'}{q}\sigma < \sigma$.
Sau đó, người ta có thể tăng sai số này lên một số độ lệch chuẩn $\sigma' > \sigma > \frac{q'}{q}\sigma$ bằng cách thêm một Gaussian thích hợp.
Điều này có nghĩa là có một phép giảm tương đối đơn giản từ $\mathsf{DLWE}_{n, m, q, \sigma}\leq \mathsf{DLWE}_{n, m, q', \sigma'}$ vì $\sigma' > \sigma$ và $q' \mid q$ (trường hợp của $q' < q$ không khó hơn nhiều, nhưng bạn phải xử lý một số "lỗi làm tròn"), vì vậy lợi thế sẽ nhỏ hơn.
