Lăsa $q \geq 2$ fi un întreg prim. Luați în considerare două funcții, date de:
$$f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q),$$
$$g(b, x) = Ax + b \cdot (As + e') + e~~~(\text{mod}~q),$$
unde avem:
\begin{align}
b &\în \{0, 1\}, \
x &\în \mathbb{Z}_{q}^{n}, \
s &\în \mathbb{Z}_{q}^{m}, \
A &\în \mathbb{Z}_{q}^{n \times m}, \
e' &\în \mathbb{Z}_{q}^{m}, \
u &\in \mathbb{Z}_{q}^{m},
\end{align}
$e$ este eșantionat din distribuție:
\begin{ecuație}
D_{\mathbb{Z}_q, B^{'}}(x) = \frac{e^{\frac{- \pi ||x||^{2}}{B^{'2}}} }{\sum_{x \in \mathbb{Z}_q^{n}, ||x|| \leq B'} e^{\frac{- \pi ||x||^{2}}{B^{'2}}}},
\end{ecuație}
Unde
$$B' = \frac{q}{C_{T} \sqrt{mn \log q}},$$
$C_{T}$ este o constantă fixă.
În acest lucrare, functiile sunt definite in ecuatia 29 si se mentioneaza ca in cel mai rau caz peste $A$, $u$ și $e'$, presupunând că LWE este greu pentru algoritmii clasici de timp polinomial, făcând distincție între $f$ și $g$ este, de asemenea, greu, dat $A$ și au dat (polinom multe) „probe” (din moment ce $e$ este o distribuție de probabilitate, ieșiri de $f$ sau $g$ sunt mostre) de la oricare $f$ sau $g$.
Reducerea LWE este valabilă și pentru cazul mediu.
Lucrarea menționează, de asemenea, că aceste două funcții sunt o familie de „funcții extinse fără gheare de trapă (Definiția 5, 6, 7.)”
Ca referință la dovada acestor fapte de mai sus, lucrarea face referire acest hârtie (Lema 9.3). Cu toate acestea, în timp ce demonstrează Lema 9.3, a doua lucrare face referire și la alte lucrări, cum ar fi acest unu. Dovada nu mi-a fost clară în nicio ziare.
Am vrut să întreb cum să reduc sarcina de a face distincția între $f$ și $g$ la LWE. De asemenea, am vrut să întreb despre importanța funcției de a fi „extens trap-door claw free” în acea reducere.
Din înțelesul meu, duritatea LWE spune că dacă ni se dă $A$, făcând distincție între eșantioane uniform aleatoare și mostre din $As + e'$ e greu. Nu sunt sigur cum $b$ și $x$ sau ceilalți parametri iau în considerare acest fapt. Este acolo unde avem nevoie de dovada fără gheare de capcană extinsă?
