Poti. Există o anumită avertizare care ar trebui menționată aici --- problemele LWE duritatea este controlată (parțial) de mărimea modulului $q$.
Două regimuri parametrice importante sunt $q$ fiind polinomial mare în parametrul de securitate și super-polinom mare.
Modul mai mic este mai bun atât pentru eficiență, cât și pentru securitate.
Cred că doar recent avem PRF-uri cu modul polinomial de la LWE, vezi de exemplu acest.
Până la acea lucrare, acest lucru a condus la situația amuzantă în care am putea construi lucruri precum FHE nivelat dintr-o presupunere a rețelei mai slabă decât ceea ce aveam nevoie pentru a construi un PRF.
Pentru super-poli $q$ totuși, există construcții simple.
Această hârtie este o referință bună.
Ideea cheie este că un eșantion LWE $(a, \langle a,s\rangle + e)$ este pseudo-aleatoare, deci este plauzibil baza pentru un PRF.
Dacă cineva încearcă să noteze un candidat natural, cum ar fi:
$$F_s(a) = \langle a,s\rangle + e\bmod q$$
sunt doua probleme evidente:
aceasta este doar pseudoaleatoare dacă $a$ este aleatoriu (deci acesta este un „PRF slab” mai degrabă decât un PRF --- doar o primitivă criptografică ușor diferită)
$F_s(a)$ este o funcție randomizată --- eroarea $e$ trebuie alese aleatoriu.
Puteți rezolva această a doua problemă rotunjind-o la cel mai apropiat multiplu de $p$, adică scrisul $F_s'(a) = \lfloor \langle a,s\rangle + e\rceil_p$.
Cu conditia ca $q/p$ este suficient de mare, alegerea aleatorie a $e$ va avea un impact doar neglijabil deseori asupra rezultatului final, așa că putem scrie și funcția (deterministă). $F_s'(a) = \lfloor \langle a,s\rangle\rceil_p$.
Alternativ, acesta poate fi văzut ca un PRF slab construit din Învățarea cu rotunjire presupunere.
Pentru a „actualiza” PRF-ul slab la un PRF standard, se poate face cheia să fie $(A, S_1, \dots, S_k)$, și definiți
$$F_{A, S_1,\dots, S_k}(x_1,\dots,x_k) = \left\lfloor A\prod_{i =1}^k S_i^{x_i}\right\rceil_p.$$
Unde $x_i\in\{0,1\}$, și $A, S_1,\puncte, S_k$ sunt fie elemente inelare, fie matrice cu dimensiuni adecvate, astfel încât expresia să aibă sens.
Aceasta este tocmai construcția făcută în a doua lucrare din secțiunea 5.
În concluzie:
- da putem construi PRF-uri din probleme LWE/latice
- A face acest lucru eficient (de la modul mic) a fost surprinzător de greu, dar acum se știe cum se face (vezi prima lucrare)
- A face acest lucru din problema LWR este conceptual simplu, dar putem baza securitatea problemei LWR doar pe problema LWE pentru modul mare.
