Các thông số trong RLWE

Để cho $n, q, \sigma$ là bậc của đa thức ($x^n+1$), modulo hệ số và đạo hàm tiêu chuẩn tương ứng. Tôi thường thấy một số thông số như

Đối với RLWE, chúng ta có thể sử dụng CRT để phân tách $\text{RLWE}_{q}$ đến một số $\text{RLWE}_{q_i}$ vì $1\leq i\leq l$, ở đâu $q = q_1 q_2\cdots q_l$, thì khi xem xét tính bảo mật của RLWE, chúng ta nên thực hiện $\log q$ hoặc $\log q_i$ được cân nhắc?

Bạn nên xem xét $\log q$.

Xem xét rằng tất cả các tham số khác là cố định, càng nhỏ $q$ là, cao hơn là bảo mật. Ngay cả bảng trong câu hỏi của bạn cũng hiển thị điều này (bảng có thể cho rằng $\sigma$ là một giá trị cố định nhỏ).

Độ cứng của các bài toán LWE và RLWE tăng theo tỷ lệ $q / || \text{noise}||$ giảm, tức là, tiếng ồn lớn hơn cho cùng một $q$ làm cho (R)LWE khó hơn. Bạn có thể nghĩ về hai trường hợp cực đoan: nếu tiếng ồn bằng 0, thì bạn có thể tìm ra bí mật $s$ với việc loại bỏ Gaussian; nếu tiếng ồn lớn như $q$, thì về cơ bản là không thể tìm thấy $s$ bởi vì mọi thứ sẽ (rất gần) đồng nhất.

Vì vậy, nếu bạn lấy mẫu (R)LWE của mình $(a, b)$ chế độ xác định $q$ và giảm mod nhỏ hơn $q'$ (điều đó chia $q$), các mẫu mới của bạn có cùng thuật ngữ tiếng ồn, nhưng đối với mô đun nhỏ hơn, do đó tỷ lệ $q' / || \text{noise}||$ nhỏ hơn và Ví dụ (R)LWE mà bạn nhận được khó hơn.