Paradigme pentru generatoare pseudoaleatoare necondiționate

Titlul original:

Paradigms for Unconditional Pseudorandom Generators

Conținutul cărții:

În acest studiu cuprinzător al generatoarelor pseudoaleatorii necondiționate (PRG), autorii prezintă cititorului o introducere intuitivă la unele dintre cele mai importante cadre și tehnici de construire a PRG necondiționate pentru modelele de calcul restrânse. Autorii discută patru paradigme majore pentru proiectarea PRG-urilor: mai multe PRG-uri bazate pe generatoare uniforme k-wise, generatoare cu polarizare mică și combinații simple ale acestora, mai multe PRG-uri bazate pe „reciclarea” biților aleatori pentru a profita de blocajele de comunicare, conexiuni între PRG-uri și dificultatea de calcul și cadre PRG bazate pe restricții aleatorii.

Autorii explică modul de utilizare a acestor paradigme pentru a construi PRG-uri care funcționează necondiționat, fără ipoteze matematice nedovedite. Construcțiile PRG utilizează ingrediente precum aritmetica câmpurilor finite, grafurile de expansiune și extractorii de aleatoriu.

Analizele utilizează tehnici precum analiza Fourier, aproximatorii de tip sandwich și lemmele de simplificare sub restricții. Paradigme pentru generatoare pseudoaleatoare necondiționate oferă cititorului o bază într-un subiect important utilizat pe scară largă în informatică teoretică și criptografie.