Đầu tiên, rõ ràng là người ta luôn có thể tăng tiếng ồn trong phiên bản LWE mà không ảnh hưởng đến bảo mật, do đó (đối với mô-đun cố định), tỷ lệ mô-đun trên nhiễu lớn hơn ngụ ý bảo mật "không tệ hơn".
Tất nhiên, điều này không giải thích tại sao bảo mật nên thay đổi đối với $\sigma/q$, thay vì một số biểu thức phức tạp hơn.
Có hai lý do để thấy tại sao đây là cách "đúng" để đo kích thước của tiếng ồn.
Đầu tiên là nó là những gì xuất hiện trong trường hợp xấu nhất đến giảm trường hợp trung bình.
Ví dụ, Giảm ban đầu của Regev chỉ ra rằng:
Định lý 1.1 (Chính thức) Để cho $n, p$ là số nguyên và $\alpha\in(0,1)$ được như vậy mà $\alpha p >2\sqrt{n}$. Nếu tồn tại một thuật toán hiệu quả để giải quyết $LWE(p, \Psi_\alpha)$ thì tồn tại một thuật toán lượng tử hiệu quả xấp xỉ phiên bản quyết định của bài toán vectơ ngắn nhất (GAPSVP) và bài toán vectơ độc lập ngắn nhất (SIVP) trong phạm vi $\tilde{O}(n/\alpha)$ trong trường hợp xấu nhất.
Lưu ý rằng $1/\alpha$ là tỷ lệ "mô-đun trên tiếng ồn", do đó, hệ số gần đúng mà người ta phải giả định là khó có thể chia tỷ lệ trực tiếp với $1/\alpha$.
Tuy nhiên, trong thực tế, người ta không muốn kêu gọi cụ thể việc giảm trường hợp xấu nhất thành trường hợp trung bình khi chọn tham số, vì hai lý do:
$\sigma := \alpha q > 2\sqrt{n}$ là bắt buộc, vì vậy đối với $n> 500$ (là giới hạn dưới thoải mái) người ta cần $\sigma > 40$, lớn hơn nhiều so với người ta sử dụng trong thực tế.
Ngoài ra còn có một "khoảng cách chặt chẽ" trong việc giảm, xem phần 6 của Một cái nhìn khác về sự chặt chẽ 2). Điều này chỉ tác động đến "các hằng số" trong việc giảm, nhưng tác động là khá lớn và để hấp dẫn việc giảm, người ta phải chọn các tham số khá kém hiệu quả.
Vì vậy, làm thế nào chúng ta có thể nói rằng một cách cụ thể rằng tỷ lệ mô-đun trên tiếng ồn nhỏ hơn trong LWE ngụ ý bảo mật tốt hơn?
Có hai điểm ở đây:
Mô-đun của LWE không ảnh hưởng nhiều đến tính bảo mật của nó, xem ví dụ cor 3.2 của Độ cứng cổ điển của LWE.
Bạn có thể tham số hóa rõ ràng các cuộc tấn công đã biết theo tỷ lệ mô-đun trên tạp âm, xem chương 4 của Luận án Rachel Player, hoặc công cụ ước tính LWE.
Lưu ý rằng đây là câu chuyện dành cho LWE. Bạn cũng đã sử dụng thẻ cho Ring LWE. Mọi thứ ở đó phức tạp hơn một chút và có thể phụ thuộc vào "hành vi phân tách" của mô đun $q$ trong bất kỳ lĩnh vực số nào bạn đang làm việc, mặc dù tôi là người sai khi viết câu trả lời về chủ đề này.
