Problema Learning Parity with Noise (LPN) este următoarea
Lăsa $\vec s\in\mathbb{F}_2^n$ să fie un secret fix și $\mathcal{O}_{\vec s}$ fi un oracol care probe $\vec a_i\obține \mathcal{U}(\mathbb{F}_2^n)$, $e_i \gets \mathsf{Berna}(\tau)$, și se întoarce $(\vec a_i, \langle \vec a_i, \vec s\rangle + e_i)$
Problema LPN (căutare) este că se acordă acces la interogare la oracol $\mathcal{O}_{\vec s}$, pentru a recupera secretul $\vec s$.
Dacă restricționați anumite interogări legate de $m$ de câte ori suni $\mathcal{O}_{\vec s}$, problema este tocmai problema care vă interesează.
Când rata de zgomot $\tau$ este constantă (în funcție de $n$), iirc cea mai cunoscută complexitate pentru rezolvarea LPN este algoritmul Blum, Kalai, Wasserman (BKW), care rulează în timp, memorie și complexitatea probei $2^{O(n/\log n)}$.
Deci nu ar trebui (asimptotic) să ne așteptăm la complexitate poli-timp.
Concret însă, pentru destul de mici $p$ situatia este tratabila. Pentru mai multe citiri despre aceasta, vezi LPN decodificat.
Am inclus mai jos o imagine a timpului de rulare a diverșilor algoritmi LPN.
Aici, $\tau \in [0, 1/2]$ este „rata de zgomot” și poate fi scris ca $\tau = \min(p, 1-p)$ în notația dvs.
Rețineți că pentru $p = 0,99 $, avem asta $\tau = 1 / 100$.
Apoi teorema 5 a lucrării legate rezolvă LPN cu complexitatea timp/interogare
$$\tilde{\Theta}\left(\left(\frac{1}{(1-\tau)^n}\right)^{\frac{1}{1+\log\left(\frac{ 1}{1-\tau}\right)}}\right).$$
Acest lucru dă complexitate timp/interogare $\aproximativ (100/99)^{\frac{n}{1+\log(100/99)}}$, care, deși nu este un timp polinom, ar trebui să fie destul de rezonabil pentru dimensiuni moderate $n$.
