Profesorul dumneavoastră vorbește despre următoarea optimizare relativ comună
Lăsa $\mathcal{K}$ fii un set și lasă $\mathsf{Eșantion} : \{0,1\}^r\la\mathcal{K}$ fi un algoritm care, la intrare $r$ biți uniform aleatori, scoate un element $k\în \mathcal{K}$.
Dacă $\mathsf{PRG} : \{0,1\}^s\la\{0,1\}^r$ este un PRG, atunci pt $s\leftarrow\{0,1\}^s, r\leftarrow\{0,1\}^r$, distribuțiile de
$$\mathsf{Eșantion}(\mathsf{PRG}(e))\approx_c \mathsf{Eșantion}(r)$$
nu se pot distinge din punct de vedere computațional.
Dovada acestui lucru este aproximativ banală. Prin securitatea PRG, $\mathsf{PRG}(s) \approx_c r$. Aplicarea algoritmului (eficient). $\mathsf{Eșantion}$ menține indistincbilitatea computațională (ca altfel $\mathsf{Eșantion}$ ar fi un adversar eficient împotriva PRG).
În esență, dacă construcția finală are nevoie de un $s$-bit cheie, adesea poate fi suficient ca cheia să fie a $r$-bit PRG sămânță, și apoi întindeți acest lucru la $s$ biți cu PRG.
Există o serie de detalii specifice de subliniat în cele de mai sus:
Cheia finală generată din $\mathsf{Eșantion}(r)$ nu trebuie să fie în mod uniform aleatoriu (deși acesta este cel mai frecvent caz de departe).
Se pot slăbi și mai mult ipotezele privind rezultatul de mai sus --- apelând la extractoare aleatorii, intrarea $r$ în sine nu trebuie să fie uniformă, ci în schimb necesită „entropie minimă suficientă” într-un mod care poate fi făcut precis.
Mai aveți nevoie de schimb de chei. Jocul de securitate al PRG-urilor necesită ca sămânța PRG să fie păstrată secretă pentru ca securitatea să o păstreze, așa că trebuie să vă asigurați că Eve nu obține acces la sămânță (așa cum menționați).
Tot ceea ce spune această optimizare este că „sarcina utilă” a schimbului de chei poate fi făcută să fie mai mică folosind un PRG (în special, poate fi $r$ biți mai degrabă decât $s$ biți).
Există o optimizare aferentă (care este diferită într-un mod subtil) despre care ar putea merita și ea discutată.
Adesea, în criptografie (în special, în criptografia bazată pe rețea și codificare) trebuie să transmiteți un element mare, uniform aleatoriu.
În special, ipoteza Învățare cu erori este despre „eșantioane” LWE:
$$ (A, As+e)$$
Nu mă voi deranja să definesc totul în acest eșantion și, în schimb, spun asta $A$ este de obicei o matrice uniform aleatorie, de dimensiune $\aproximativ 1-10 kb$, în funcție de schema particulară.
Ați putea fi tentat să înlocuiți acest obiect uniform aleatoriu cu o sămânță PRG $s$, pe care apoi se poate extinde în mod determinist la valoarea aleatorie $A$ mai tarziu. Deoarece semințele PRG sunt de ordinul $\aproximativ 128$ biți, acesta este un câștig (potențial) semnificativ.
Totuși, aceasta nu este o optimizare validă, din cauza celui de-al treilea punct de mai sus --- nu puteți folosi un PRG pentru a „comprima” o valoare uniform aleatorie într-o sămânță scurtă în acest fel, dacă schema dvs. face publică ulterior această valoare uniform aleatorie. Sau puteți, dar pentru anumite PRG-uri, acest lucru poate distruge complet securitatea.
Există încă lucruri similare pe care le puteți face cu lucruri numite funcții de ieșire extensibile (din orice motiv, acronimul este XOF). Acestea sunt primitive bazate pe hashing care (aproximativ) sunt menite să fie folosite atunci când se dorește proprietăți asemănătoare PRG, dar cu o sămânță publică.
Oricum, utilizarea unui XOF pentru a comprima o valoare mare uniform aleatorie este o optimizare incredibil de comună. Sunt destul de sigur că ambii finaliști NIST PQC bazați pe LPR (Sabre/Kyber) folosesc această optimizare, deși orice implementare anume ar putea abate ușor de la specificație și poate include/nu include optimizarea.
