Cred că acesta este doar un artefact al lui Regev care reprezintă valori în $\mathbb{T} \cong \mathbb{Z} / q\mathbb{Z} = \{0, 1/q, \dots, (q-1)/q\}$, mai degrabă decât în $\{0,1,\dots,q\}$ direct.
Mai sunt totuși câteva lucruri de menționat:
În primul rând, consensul modern este că pentru duritatea $\mathsf{LWE}$ [1], distribuția particulară a erorilor pe care o utilizați nu contează prea mult. În special, cele obișnuite (datorită ușurinței de eșantionare) sunt „binoame centrate”, sau chiar uniforme pe un anumit interval. Pentru exemple, consultați finaliștii NIST PQC.
Desigur, aceste distribuții pe care le folosim nu sunt întotdeauna justificate de reducerile de la cel mai rău caz la cel mai mediu. Deci ce dă? Avem (în linii mari) două opțiuni în ceea ce privește alegerea parametrilor:
Criptanaliza $\mathsf{SIVP}_\gamma$ direct, găsiți parametrii siguri și apoi treceți-i prin $\mathsf{SIVP}_\gamma \leq \mathsf{LWE}$ reducerea sau
Criptanaliza $\mathsf{LWE}$ direct și alegeți acești parametri.
Al doilea este mai popular de departe. Există câteva motive pentru aceasta:
Reducerea $\mathsf{SIVP}_\gamma \leq \mathsf{LWE}$ este (concret) nu foarte „strâns”. În special, duce la o inflație decent de mare a parametrilor. Acest lucru este menționat în câteva locuri, de exemplu o altă privire la etanșeitatea 2. Desigur, acest lucru se întâmplă adesea atunci când inițial se analizează în mod concret o dovadă căreia nu îi pasă de constante. Au existat lucrări ulterioare, de exemplu acest, acest, și acest, dar nimic prea mainstream. Dintre lucrări, m-am uitat cu adevărat doar la primul --- iirc pe care l-a găsit prin umflare $(n, \log_2 q, \sigma)$ printr-un factor de $\aproximativ 2$ în comparație cu ceea ce folosesc oamenii în practică, puteți obține securitate concretă de la cel mai rău caz până la o reducere medie.
Nu este clar că (în cel mai rău caz) criptoanaliza $\mathsf{SIVP}_\gamma$ este mai ușor decât criptoanaliza (caz mediu). $\mathsf{LWE}$. Acest lucru se datorează faptului că nu există un candidat evident pentru cel mai rău caz al $\mathsf{SIVP}_\gamma$! Desigur, s-ar putea folosi întotdeauna o analiză a cazului mediu ca limită inferioară a unei analize a cazului cel mai rău, dar atunci de ce analiza cazului mediu o problemă diferită de cea care vă interesează?
Toate acestea sunt pentru a spune că $\mathsf{SIVP}_\gamma \leq \mathsf{LWE}$ reducerea este (în mare parte) văzută ca afirmând că $\mathsf{LWE}$ este (calitativ) „distribuția corectă” care trebuie privită. Există multe distribuții de instanțe aleatorii pe care le-ați putea privi, iar unele ar putea fi „slab din punct de vedere structural” (pentru exemple în acest sens, consultați lucrările despre „Instanțe Poly-LWE slabe” sau pe care RSA a definit folosind o variantă aleatorie $n$-bit întreg, mai degrabă decât aleatoriu $n$-bit semiprime, ar fi „distribuția greșită” de utilizat din motive structurale). The $\mathsf{SIVP}_\gamma \leq \mathsf{LWE}$ reducerea poate fi interpretată ca fixarea unei anumite distribuții pentru $\mathsf{LWE}$, pe care noi atunci cantitativ parametrizați prin criptoanaliza (directă).
[1] Rețineți că pentru semnături, distribuția face contează, dar acest lucru se datorează detaliilor construcțiilor/dovezilor de securitate ale semnăturilor și nu în mod abstract pentru că credem că $\mathsf{LWE}$ este greu atunci când utilizați gaussieni discreti și nu gaussieni rotunjiți/variabile aleatoare uniforme sau orice altceva.
