Parametrii în RLWE

Lăsa $n, q, \sigma$ fie gradul polinom($x^n+1$), coeficientul modulo și, respectiv, derivația standard. Văd adesea câțiva parametri precum

Pentru RLWE, putem folosi CRT pentru a descompune $\text{RLWE}_{q}$ unora $\text{RLWE}_{q_i}$ pentru $1\leq i\leq l$, Unde $q = q_1 q_2\cdots q_l$, atunci când luăm în considerare securitatea RLWE, ar trebui să luăm $\log q$ sau $\log q_i$ a fi considerat?

Ar trebui să luați în considerare $\log q$.

Avand in vedere ca toti ceilalti parametri sunt fix, cu atat mai mici $q$ este, cu atât securitatea este mai mare. Chiar și tabelul din întrebarea dvs. arată acest lucru (tabelul presupune probabil că $\sigma$ este o valoare fixă ​​mică).

Duritatea problemelor LWE și RLWE crește odată cu raportul $q / || \text{zgomot}||$ scade, adică zgomot mai mare pentru același $q$ face (R)LWE mai greu. Te poți gândi la cele două cazuri extreme: dacă zgomotul este zero, atunci poți găsi secretul $s$ cu eliminare gaussiana; dacă zgomotul este la fel de mare ca $q$, atunci este practic imposibil de găsit $s$ pentru că totul va fi (foarte aproape de) uniform.

Deci, dacă vă luați mostrele (R)LWE $(a, b)$ mod definit $q$ și reduceți modul mai mic $q'$ (care se împarte $q$), noile dvs. mostre au aceiași termeni de zgomot, dar cu privire la un modul mai mic, deci raportul $q' / || \text{zgomot}||$ este mai mic și cel Exemplul (R)LWE pe care îl primiți este mai greu.