Sunt nou în criptografie și încerc să înțeleg formal conceptele LWE (învățare cu erori). Voi declara înțelegerea mea cu privire la definiții, care ar putea fi incorecte.
Definiții conform înțelegerii mele
Lăsa $R$ fi un inel comutativ unitar finit echipat cu o probabilitate $\mu$ (a caror $\sigma$-algebra este discretă). $R$ se spune că satisface ipoteza LWE de căutare în cel mai rău caz dacă pentru toate polinoamele $n$ și tot algoritmul randomizat în timp polinomial $S$, harta
\begin{ecuație}
m\mapsto \min_{s\in R^m} p(m,s)\text{,}
\end{ecuație}
Unde
\begin{ecuație}
p(m,s) = \Pr\{(A,e)\in R^{m\times n(m)} \times R^{n(m)}: S (-sA+e,A)= s\}\text{,}
\end{ecuație}
este neglijabilă. În ecuația de mai sus, $A$ este eșantionat din probabilitatea uniformă și $e$ este eșantionată din probabilitatea produsului $\mu^{n(m)}$.
$R$ se spune că satisface ipoteza LWE de decizie în cel mai rău caz dacă pentru toate polinoamele $n$ și tot algoritmul randomizat în timp polinomial $D$, harta
\begin{ecuație}
m\mapsto \min_{s\in R^m} |p_1(m,s)-p_2(m)|\text{,}
\end{ecuație}
Unde
\begin{ecuație}
\begin{split}
p_1(m,s) &= \Pr\{(A,e)\in R^{m\times n(m)}\times R^{n(m)}: D (-sA+e,A) =1\},\
p_2(m) &= \Pr\{(b,A)\in R^{n(m)}\times R^{m\times n(m)}\times: D (b,A)=1\ }\text{,}
\end{divizat}
\end{ecuație}
este neglijabilă. În ecuația de mai sus, $A$ și $b$ sunt eșantionate din probabilitățile uniforme și $e$ este eșantionată din probabilitatea produsului $\mu^{n(m)}$.
Întrebare
Am dovedit că dacă $R$ este un câmp finit echipat cu o probabilitate $\mu$ (a caror $\sigma$-algebra este discretă) iar dacă $R$ satisface ipoteza LWE de căutare în cel mai rău caz $R$ satisface, de asemenea, ipoteza LWE de decizie în cazul celui mai rău caz. Dar cum se dovedește contrariul? Toată literatura pe care am văzut-o până acum spune doar că este banală, dar nu am putut să o dovedesc. Mai explicit, am nevoie de o dovadă a următoarei afirmații:
Dacă $R$ este un inel comutativ unitar finit echipat cu o probabilitate $\mu$ (a caror $\sigma$-algebra este discretă) iar dacă $R$ satisface, deci, ipoteza LWE pentru cea mai nefavorabilă decizie $R$ satisface, de asemenea, ipoteza LWE de căutare în cel mai rău caz.
Încercarea mea
Asuma ca $R$ satisface ipoteza LWE pentru cea mai nefavorabilă decizie. Lăsa $n$ fi un polinom și fie $S$ să fie un algoritm randomizat în timp polinomial (ale cărui intrări sunt elemente în $R^{n(m)}\ori R^{m\n(m)}$ și ale căror ieșiri sunt elemente în $R^m$). Trebuie să arătăm că harta
\begin{ecuație}
m\mapsto \min_{s\in R^m} p(m,s)\text{,}
\end{ecuație}
Unde $p(m,s)$ este definit mai sus, este neglijabil. Dată o intrare $(b,A)\în R^{n(m)}\ori R^{m\n(m)}$ Unde $b=-sA+e$, $S$ va întoarce o ghicire $g\în R^m$ care ar putea sau nu este egal $s$. Se poate calcula $b+gA$ și notează-l prin $e'$. Dacă $g=s$, atunci $e'=e$. Dacă $g\neq s$, atunci $e'=e$ ar putea sau nu ține.Nu stiu ce sa fac acum.
