Thực sự không có "mối quan hệ" giữa hai tham số này, do cái được gọi là chuyển đổi mô-đun.
Đại khái, đưa ra một ví dụ LWE $\bmod q$, người ta có thể thay đổi nó thành một phiên bản LWE $\bmod p$ với chi phí tương đối thấp, cho nhiều loại $p$.
Có nhiều kết quả dọc theo những dòng này, nhưng tôi sẽ mô tả một kết quả từ Mức giảm từ trường hợp xấu nhất đến trường hợp trung bình đối với mạng mô-đun.
Để cho $\psi$ là một số phân phối xác suất trên $\mathbb{T}_{R^\vee}$, và $s\in(R^\vee_q)^d$ là một véc tơ. Chúng tôi xác định $A^{(M)}_{q,s,\psi}$ như
phân phối trên $(R_q)^d à \mathbb{T}_{R^\vee}$ thu được bằng cách chọn một vectơ a $s\in(R_q)^d$ ngẫu nhiên đều và $e \in \mathbb{T}_{R^\vee}$
dựa theo $\psi$, và trở về $(a, \frac{1}{q}\langle a, s\rangle + e)$.
MLWE: Cho một số nguyên $q \geq 2$ và phân phối $\Psi$ trên một họ phân phối trên $K_\mathbb{R}$. Phiên bản quyết định
vấn đề học mô-đun có lỗi $M-LWE_{q, \Psi}$ như sau: Hãy $s \in (R^\vee_q)^d$ là ngẫu nhiên thống nhất và
$\psi$ được lấy mẫu từ $\Psi$ ; Mục đích là để phân biệt giữa nhiều mẫu độc lập tùy ý từ $A^{(M)}_{q, s, \psi}$và cùng một số mẫu độc lập từ $U(R^d_q, \mathbb{T}_{R^\vee})$.
Điều này tổng quát hơn RLWE và giảm xuống RLWE khi $d = 1$.
Gia đình phân phối $\Psi_a$ là một phân phối Gaussian hình elip nhất định, xem phần 2.3.
Dù sao, kết quả chuyển đổi mô đun là định lý 4.8.
Đây, $N = thứ$ là "tổng kích thước" của phiên bản MLWE.
Cài đặt $n = 1$ khôi phục trường hợp của RLWE mà bạn quan tâm.
Để cho $p, q \in [2, 2^{N^{O(1)}}
]$ và $\alpha, \beta â (0, 1)$ như vậy mà $\beta \geq \alpha \max(1, \frac{q}{p})n^{1/4}N^{1/2}\omega(\log_2 N)$
và $\alpha q \geq \omega(\sqrt{\log(N)/n})$. Tồn tại một giảm thời gian đa thức từ $M-LWE_{q,\Psi_\alpha}$ đến $M-LWE_{p,\Psi_\beta}$.
Đây là tất cả để nói rằng bạn có thể giảm từ một mô đun tùy ý $q$ đến một mô đun tùy ý khác $p$, với chi phí tăng tốc độ tiếng ồn từ $\alpha\mapsto \frac{q}{p}\alpha\sqrt{N}\omega(\log_2 N)$. Đây không phải là Tổng cộng miễn phí (có thêm $\sqrt{N}$ yếu tố), nhưng cho rằng các mô đun $q, p$ thường là các đa thức nhỏ trong $N$, chi phí bạn phải trả là tương đối nhỏ so với kích thước thông số.
Kết quả là, thực sự không có mối quan hệ giữa duy nhất mô đun bản mã (như nó thường được gọi, không phải thương số bản mã) và thứ nguyên, như bất kỳ mối quan hệ nào. Mà còn cần phải tính đến kích thước của phân phối lỗi.
Đối với cách thực sự thiết lập tất cả những thứ này, mọi người thường đưa các tham số của họ vào Công cụ ước tính LWE, đưa ra một số ước tính bảo mật bit cho từng bộ tham số cụ thể.
