Să presupunem că $n$ este o putere a doi, $q=3\pmod 8$, prim și $R=\mathbb{Z}[X]/(X^n+1)$. Denota $\Vert\cdot\Vert$ ca norma infinitului în $R_q=R/qR$ asupra coeficienților elementelor în $R_q$. Se presupune că coeficienții sunt în $[-\frac{q-1}{2},\frac{q-1}{2}]$. Voi cita doar câteva fapte pe care le voi folosi în demonstrația mea:
- $X^n+1$ factori în doi factori ireductibili modulo $q$, unde fiecare factor este de grad $n/2$ vezi Lema 3 din Aici
- Ca o consecință a faptului de mai sus, dat un fix $s\în R_q$, $s\neq 0$, numărul de distincte $a\cdot s\în R_q$, per total $a\în R_q$ este cel puțin $q^{n/2}$, așa cum se susține, dar fără dovezi riguroase din pagina 7.
Acum afirmația mea este aceea dată de un uniform aleatoriu $a\în R_q$, un eșantion RLWE $b=as+e$ (Unde $s,e$ sunt alese dintr-o distribuție Gaussiană discretă pe $\mathbb{Z}^n$ astfel încât, cu o probabilitate covârșitoare, $\Vert s\Vert, \Vert e\Vert\leq \beta$, pentru unii $\beta$) are un secret unic $s$.
Deci dovada merge prin contradicție:
- Să presupunem că dat fiind o aleatorie uniformă $a\în R_q$, Asuma ca $b=as+e=as^\prime+e^\prime$, Unde $s\neq s^\prime$ și $s,s^\prime,e,e^\prime$ sunt alese din distribuția Gaussiană discretă de mai sus astfel încât toate normele lor să fie $\leq \beta$ cu o probabilitate copleșitoare.
- Astfel, putem rescrie ecuația de mai sus ca $a(s-s^\prim)=(e^\prim-e)$ și susținem că acest lucru se întâmplă doar cu o probabilitate neglijabilă peste toate acestea $a,s,s^\prime,e,e^\prime$.
- Procedăm în mai mulți pași: În primul rând, remediați $e,e^\prime,s,s^\prime$ și întrebați probabilitatea ca ecuația de mai sus să fie valabilă pentru toate $a\în R_q$, adică care este probabilitatea ca $a(s-s^\prim)=(e^\prim-e)$ pentru un mod uniform aleatoriu $a\în R_q$? Răspunsul meu la această întrebare este că din moment ce $a(s-s^\prim)$ dureaza cel putin $q^{n/2}$ valori diferite peste toate $a\în R_q$, atunci ecuația de mai sus este valabilă cu probabilitate $\leq \dfrac{1}{q^{n/2}}$.
- În cele din urmă, luăm uniunea legată peste toate $s,s^\prime,e,e^\prime$ luate din distribuția gaussiană discretă astfel încât toate să aibă norme $\leq \beta$ cu o probabilitate copleșitoare, apoi probabilitatea generală ca $a(s-s^\prim)=(e^\prim-e)$ este $\leq \dfrac{(2\beta+1)^{4n}}{q^{n/2}}$, deoarece numărul de elemente în $R_q$ care are norma infinit mai mică decât $\beta$ este $(2\beta+1)^n$ iar prin inegalitatea triunghiului.
I-am arătat această dovadă profesorului meu, dar nu are sens pentru el și am spus că fac o greșeală proastă în special la pasul 3 al dovezii mele.
În acest moment, nu văd de ce dovada mea este incorectă și nu a menționat de ce dovada mea este greșită. Am încercat să-i explic dovada mea, dar am fost închis deoarece pentru el am făcut o greșeală groaznică.
Deci, oricine poate ajuta și face lumină în această problemă este foarte apreciat.
