Vreau doar să știu dacă dovada mea este corectă, ceea ce înseamnă că dacă secretul Ring-LWE este mic, atunci este unic. Înainte de a-mi da dovada, iată un fapt:
Faptul 1: $\Pr [\Vert r \Vert_\infty \leq \beta: r\xleftarrow{\$} R_q]\leq \left(\dfrac{2\beta+1}{q}\right)^n$, Unde $R_q=\mathbb{Z}_q[X]/(X^n+1)$, Unde $n$ este o putere a doi, $q$ este un prim și $\beta$ este un număr real pozitiv.
Acum lasa $D_\sigma$ fie distribuția Gaussiană discretă pe $R=\mathbb{Z}[X]/(X^n+1)$ (care poate fi privit și ca gaussian discret pe $\mathbb{Z}^n$ prin încorporarea coeficientului din $R$ la $\mathbb{Z}^n$. Un alt fapt:
Faptul 2: $\Pr[\Vert z\Vert_\infty \leq \mathcal{O}(\sigma\sqrt{n}): z\leftarrow D_\sigma]>1-2^{-n}$ pentru alegerea adecvată a $\sigma$.
Acum să presupunem că $a\xleftarrow{\$}R_q$ și $s,e\leftarrow D_\sigma$ astfel încât $b=as+e$, prin urmare $(a,b)$ este un eșantion RLWE pentru secret $s$. Prin urmare, $\Vert s\Vert_\infty,\Vert e\Vert_\infty$ sunt ambele mai mici decât $\beta=\mathcal{O}(\sigma\sqrt{n})$ cu o probabilitate covârșitoare după Faptul 2.
Acum vreau să demonstrez că este imposibil să găsești altul $s^\prim, s^\prime\neq s$, $\Vert s^\prime\Vert_\infty\leq \beta$ astfel încât $b=as^\prime+e^\prime$, $\Vert e^\prime \Vert_\infty\leq \beta$ cu o probabilitate copleșitoare. Iată argumentul meu:
Continuați prin contradicție. Presupune $b=as^\prime+e^\prime$. (Asuma ca $a$ este un element inversabil al $R_q$, acesta este cazul cu o probabilitate covârșitoare pentru caz $q=3\pmod{8}$). Atunci $s^\prime=a^{-1}(b-e^\prime)=a^{-1}(e-e^\prime)+s$. Prin urmare, $(a^{-1},s^\prim)$ este un eșantion RLWE pentru secret $e^\prime-e$ de cand $a^{-1}$ este uniform aleatorie prin faptul că $a$ este uniform aleatorie. Prin urmare, așa $s^\prime$ nu se distinge de un element uniform aleatoriu în $R_q$ prin ipoteza decizională-RLWE. Dar prin Faptul 1, pentru $q>4\beta +2$, probabilitatea ca $\Vert s^\prime \Vert_\infty \leq \beta$ este $<2^{-n}$. Prin urmare, atât de mic $s$ este unică cu o probabilitate copleșitoare. (Acest lucru mai spune că, dacă nu punem nicio restricție asupra normei de $s$, secretul RLWE pentru $b$ nu este unic, deoarece putem construi pur și simplu astfel de $s^\prime$).
Așadar, aș dori să știu dacă argumentul meu este corect sau nu și aș aprecia orice feedback util de la cineva.
