Paradigmas para generadores pseudoaleatorios incondicionales

Título original:

Paradigms for Unconditional Pseudorandom Generators

Contenido del libro:

En este estudio exhaustivo de los generadores pseudoaleatorios incondicionales (PRG), los autores presentan al lector una introducción intuitiva a algunos de los marcos y técnicas más importantes para construir PRG incondicionales para modelos restringidos de computación. Los autores discuten cuatro paradigmas principales para diseñar PRGs: varios PRGs basados en generadores k-sabios uniformes, generadores de sesgo pequeño, y combinaciones simples de los mismos, varios PRGs basados en el «reciclaje» de bits aleatorios para aprovechar los cuellos de botella de comunicación, conexiones entre PRGs y dureza computacional, y marcos PRG basados en restricciones aleatorias.

Los autores explican cómo utilizar estos paradigmas para construir PRG que funcionen incondicionalmente, sin supuestos matemáticos no demostrados. Las construcciones de PRG utilizan ingredientes como la aritmética de campos finitos, los grafos expansores y los extractores de aleatoriedad.

Los análisis utilizan técnicas como el análisis de Fourier, aproximadores de emparedamiento y lemas de simplificación bajo restricciones. Paradigms for Unconditional Pseudorandom Generators ofrece al lector una base en un importante tema ampliamente utilizado en informática teórica y criptografía.