Nu există cu adevărat o „relație” între acești doi parametri, din cauza a ceea ce se numește comutarea modulului.
Aproximativ, având în vedere o instanță LWE $\bmod q$, se poate schimba într-o instanță LWE $\bmod p$ la un cost relativ mic, pentru o mare varietate de $p$.
Există multe rezultate în acest sens, dar voi descrie unul din Reduceri de la cel mai rău caz la mediu pentru rețelele de module.
Lăsa $\psi$ fie o distribuție de probabilitate pe $\mathbb{T}_{R^\vee}$, și $s\in(R^\vee_q)^d$ fi un vector. Noi definim $A^{(M)}_{q,s,\psi}$ dupa cum
distributie pe $(R_q)^d à \mathbb{T}_{R^\vee}$ obtinut prin alegerea unui vector a $s\in(R_q)^d$ uniform la întâmplare și $e \in \mathbb{T}_{R^\vee}$
conform $\psi$, și revenind $(a, \frac{1}{q}\langle a, s\rangle + e)$.
MLWE: Pentru un număr întreg $q \geq 2$ și o distribuție $\Psi$ peste o familie de distribuiri peste $K_\mathbb{R}$. Versiunea de decizie a
problema Module Learning With Error $M-LWE_{q, \Psi}$ este după cum urmează: Fie $s \in (R^\vee_q)^d$ fie uniform aleatoriu și
$\psi$ fi prelevat din $\Psi$ ; Scopul este de a distinge între arbitrar multe mostre independente din $A^{(M)}_{q, s, \psi}$, și același număr de mostre independente din $U(R^d_q, \mathbb{T}_{R^\vee})$.
Acest lucru este mai general decât RLWE și se reduce la RLWE când $d = 1$.
Familia distribuțiilor $\Psi_a$ sunt o anumită distribuție eliptică Gaussiană, vezi secțiunea 2.3.
Oricum, rezultatul comutării modulului este teorema 4.8.
Aici, $N = nd$ este „dimensiunea totală” a instanței MLWE.
Setare $n = 1$ recuperează cazul RLWE, care vă interesează.
Lăsa $p, q \in [2, 2^{N^{O(1)}}
]$ și $\alpha, \beta â (0, 1)$ astfel încât $\beta \geq \alpha \max(1, \frac{q}{p})n^{1/4}N^{1/2}\omega(\log_2 N)$
și $\alpha q \geq \omega(\sqrt{\log(N)/n})$. Există o reducere a timpului polinomial de la $M-LWE_{q,\Psi_\alpha}$ la $M-LWE_{p,\Psi_\beta}$.
Toate acestea înseamnă că puteți reduce de la un modul arbitrar $q$ la un alt modul arbitrar $p$, cu pretul umflarii ratei de zgomot de la $\alpha\mapsto \frac{q}{p}\alpha\sqrt{N}\omega(\log_2 N)$. Asta nu este intru totul gratuit (există un suplimentar $\sqrt{N}$ factor), dar având în vedere că modulele $q, p$ sunt de obicei polinoame mici în $N$, costul pe care îl plătiți este relativ mic în comparație cu dimensiunile parametrilor.
Ca rezultat, nu există într-adevăr o relație între modulul textului cifrat (cum este numit în mod obișnuit, nu coeficientul textului cifrat) și dimensiune, ca orice relație. de asemenea trebuie să ia în considerare dimensiunea distribuției erorilor.
În ceea ce privește modul de a seta de fapt toate aceste lucruri, oamenii de obicei își introduc parametrii în Estimator LWE, care oferă o estimare a securității biților pentru fiecare set de parametri particular.
