Paradigmi per i generatori di pseudorandom incondizionati

Titolo originale:

Paradigms for Unconditional Pseudorandom Generators

Contenuto del libro:

In questa rassegna completa dei generatori pseudorandom incondizionati (PRG), gli autori presentano al lettore un'introduzione intuitiva ad alcune delle più importanti strutture e tecniche per la costruzione di PRG incondizionati per modelli ristretti di calcolo. Gli autori discutono quattro principali paradigmi per la progettazione di PRG: diversi PRG basati su generatori uniformi k-wise, generatori small-bias e semplici combinazioni di questi, diversi PRG basati sul “riciclo” di bit casuali per sfruttare i colli di bottiglia della comunicazione, connessioni tra PRG e durezza computazionale e strutture PRG basate su restrizioni casuali.

Gli autori spiegano come utilizzare questi paradigmi per costruire PRG che funzionano incondizionatamente, senza presupposti matematici non dimostrati. Le costruzioni di PRG utilizzano ingredienti come l'aritmetica dei campi finiti, i grafi di espansione e gli estrattori di casualità.

Le analisi utilizzano tecniche come l'analisi di Fourier, gli approssimatori a sandwich e i lemmi di semplificazione sotto restrizione. Paradigms for Unconditional Pseudorandom Generators offre al lettore una base su un argomento importante, ampiamente utilizzato in informatica teorica e crittografia.