În primul rând, au existat lucrări ulterioare la BPR, inclusiv o practică PRF și PRG. Aici „practic” înseamnă extrem de rapid --- ~5 cicluri pe octet, (și la fel de mici ca ~3 pentru PRG iirc). Acest lucru este cu un factor de 10 de AES folosind AES-NI. Există totuși câteva avertismente la acest lucru:
- Cheile sunt foarte mari
- Cred că sunt folosite instrucțiunile AVX, deci niste se folosește accelerația hardware
- Foarte mic se aleg parametrii.
Acești parametri mici sunt de așa natură încât echivalența LWR/LWE nu mai este cunoscută ca fiind valabilă [1] și, în plus, nu există cu adevărat o reducere semnificativă la o problemă a rețelei dure. Prin urmare, securitatea/parametrii sunt aleși concret analizând o mână de atacuri cunoscute. Se pare că ar fi de interes pentru tine.
- Care este relația dintre k, n și m? Cât de mari trebuie să fie p și q?
Depinde daca vrei sa fie dovedit sigur sau sigur din punct de vedere euristic. Pentru o securitate demonstrabilă, teorema 5.2 a lucrării pe care o legați pare să vă ofere exact relația pe care o doriți. Pentru securitatea euristică (folosind parametri mai mici), lucrurile relevante de urmărit sunt:
- secțiunea 4 a lucrării PRF și
- secțiunea 3 a lucrării PRG.
dar nu dau inegalități drăguțe pe care le-ai putea dori, pentru că astfel de inegalități nu sunt cunoscute.
În schimb, ei evaluează o mână de atacuri cunoscute pentru anumite alegeri de parametri.
- Cum ar fi timpul necesar celui mai cunoscut algoritm pentru a sparge securitatea acestei scale a funcției cu k, n și m?
A se vedea secțiunea 4 a lucrării PRF și secțiunea 3 a lucrării PRG, unde se fac mai multe calcule relevante.
3.a Ieșirea lui F este o matrice. Ce înseamnă entropia unei matrice?
Strict vorbind, nimic. Entropia este o proprietate a lui a distribuția probabilității, deci afirmația ar avea sens doar dacă cineva vede $F$ nu ca o matrice, ci ca o distribuție peste matrice. Pentru a vă face o idee despre ceea ce spun autorii, haideți $q = p_0 p_1$ fi semiprim.
Atunci, dacă $A, S_1,\puncte S_k$ sunt distribuite astfel încât (cu probabilitatea 1):
- $A\bmod p_0 \equiv 0$, și
- $S_i\bmod p_1\equiv 0$ pentru toți $i$,
atunci $F(A, S_1,\dots, S_k) \equiv 0\bmod q$ în mod constant, astfel încât PRF-ul va fi previzibil. Restricția la $A, S_i$ fiind inversabilă $\bmod q$ oprește această problemă (potențială) specială (și poate mai mult).
3.b Și această afirmație indică faptul că F este o funcție unu la unu?
Nu, dar nu se așteaptă să fie.Noi vrem $F$ a nu se distinge de a functie aleatorie. Rețineți că funcțiile aleatoare nu sunt 1-1 (puteți cuantifica acest lucru printr-o tehnică numită "Comutare PRP-PRF", dar acest lucru nu este deosebit de relevant).
[1] Rețineți că pentru majoritatea primitivelor „practice” bazate pe zăbrele, acesta este deja cazul --- de exemplu SABRE se bazează pe securitatea concretă a MLWR cu module mici, deși modulele sale de $2^{13}\aproximativ 8k$ este mult mai mare decât modulele de $q = 257$ pe care aceste PRF/PRG-uri le folosesc. Acest lucru este oarecum relevant, deoarece s-a discutat recent că LWR cu module mici nu a fost criptoanalizat deosebit de bine. Vedea acest thread de grup Google NIST PQC. De când acest thread din ~decembrie, oamenii au făcut câteva experimente (și nu au găsit nimic neașteptat), dar din fir se pare că oamenii nu au încercat să criptoanalizeze direct LWR cu module mici până acum o lună sau două.
Există câteva situații în care se pot folosi primitive practice bazate pe LWR și se pot obține securitatea dovedibilă bazată pe probleme de rețea, dar singurul „standard” pe care îl cunosc este cel al lui Sam Kim. PRF bazat pe zăbrele (cheie homomorfă).. Hart Montgomery are și un Versiune non-standard a LWR el poate dovedi securitate pentru.
