Hasta donde yo sé, la mayoría de las implementaciones de generación de números pseudoaleatorios en la práctica utilizan métodos como los registros de retroalimentación de desplazamiento lineal (LSFR) o estos algoritmos "Mersenne Twister". Si bien pasan muchas pruebas estadísticas (heurísticas), no hay garantías teóricas de que parezcan pseudoaleatorias para, por ejemplo, todas las pruebas estadísticas computables de manera eficiente. Sin embargo, estos métodos se usan indiscriminadamente en todo tipo de aplicaciones, desde protocolos criptográficos hasta computación científica y banca (probablemente). Me parece un poco preocupante que tengamos poca o ninguna garantía sobre si estas aplicaciones funcionan según lo previsto (porque cualquier tipo de análisis probablemente habría asumido una aleatoriedad verdadera como entrada).
Por otro lado, la teoría de la complejidad y la criptografía proporcionan una teoría muy rica de pseudoaleatoriedad, e incluso tenemos construcciones candidatas de generadores pseudoaleatorios que engañarían CUALQUIER prueba estadística eficiente que se te ocurra, utilizando funciones candidatas de una vía.
Mi pregunta es: ¿esta teoría ha llegado a la práctica? Espero que para usos importantes de la aleatoriedad, como la criptografía o la computación científica, se utilicen PRG teóricamente sólidos.
Por otro lado, pude encontrar un análisis limitado de qué tan bien funcionan los algoritmos populares, como el método de clasificación rápida, cuando se usan LSFR como fuente de aleatoriedad, y aparentemente funcionan bien. Ver "Algoritmos aleatorios y números pseudoaleatorios" de Karloff y Raghavan .
Respuestas:
La noción de generadores pseudoaleatorios "teóricamente sólidos" no está realmente bien definida. Después de todo, ningún generador pseudoaleatorio tiene una prueba de seguridad. No sé si podemos decir que un generador pseudoaleatorio basado en la dureza de factorizar enteros grandes es "más seguro" que, por ejemplo, usar AES como un generador pseudoaleatorio. (De hecho, existe la sensación de que es menos seguro, ya que conocemos algoritmos de factorización cuántica pero no algoritmos cuánticos para romper AES).
De lo que sí tenemos pruebas matemáticas es de varios resultados de composición, que dicen que si compones cifrados de bloque o funciones hash de ciertas maneras, puedes obtener generadores pseudoaleatorios o función pseudoaleatoria. Algunos de estos resultados se usan ampliamente en la práctica, por ejemplo, HMAC . Pero es cierto que los resultados que alcanzan un PRG y comienzan con solo suponer que el componente básico es una función unidireccional simple no son lo suficientemente eficientes para usar en aplicaciones (y esto es al menos en parte inherente) Por lo tanto, normalmente tenemos que asumir una función PRG / stream cipher / block-cipher / hash como primitiva básica, y comenzar a construir otras cosas a partir de ella. El problema no es realmente sobre el análisis asintótico, ya que esencialmente todas las reducciones criptográficas (excepto quizás el PRG universal de Levin) pueden hacerse concretas y, por lo tanto, otorgar garantías concretas bajo supuestos concretos.
Pero aunque no se basan en funciones unidireccionales, hay un sentido en el cual las construcciones como AES son "teóricamente sólidas" porque: (1) Hay conjeturas formales sobre su seguridad. (2) Hay trabajo para tratar de refutar estas conjeturas, y también derivar implicaciones de ellas.
Y, de hecho, las personas son conscientes de que para muchas aplicaciones, no sería inteligente utilizar PRG como LSFR que no satisfacen (1) y (2) anteriores.
fuente
Parece confundir la teoría con la práctica. Un generador pseudoaleatorio teóricamente adecuado encaja mal para un uso práctico por varias razones:
En contraste con esto, los generadores pseudoaleatorios reales son rápidos y vienen en diferentes sabores dependiendo de su uso. Para uso no criptográfico, casi cualquier cosa que no sea un LFSR simple hará el trabajo, no de manera demostrable, pero en la práctica (lo que es más importante para las personas que usan cosas en realidad).
Para uso criptográfico, las personas intentan ser más inteligentes. En este punto, su crítica tiene sentido: no podemos saber si un generador pseudoaleatorio en particular utilizado es "seguro", y de hecho algunos viejos se han roto, por ejemplo RC4 como se usa en WEP. Sin embargo, por las razones indicadas anteriormente, el uso de un generador pseudoaleatorio teóricamente (condicionalmente) no es una solución realista. En cambio, la comunidad criptológica se basa en la "revisión por pares": otros investigadores que intentan "romper" el sistema (su definición de cuándo se rompe un cifrado es muy amplia).
Finalmente, en las aplicaciones en las que se puede invertir el dinero y la seguridad es lo suficientemente importante, digamos códigos nucleares, las personas usan ruido generado físicamente (pasado por un extractor de aleatoriedad), aunque incluso eso no está más allá de la crítica teórica.
Cuando los investigadores escriben propuestas de subvención o presentaciones de artículos, a menudo afirman que su investigación pertenece e informa a la práctica. No sé si creen en él o es solo un servicio de labios (y puede depender del investigador), pero debes tener en cuenta que la conexión es muy exagerada en los círculos académicos, por razones obvias.
Una cosa que nos limita como investigadores matemáticos es nuestro apego dogmático a la prueba formal. Usted menciona el análisis de algoritmos aleatorios alimentados por generadores pseudoaleatorios simples. Este tipo de análisis no puede extenderse a problemas del mundo real, ya que simplemente son demasiado complicados. Y, sin embargo, en la práctica, las personas resuelven incluso problemas NP difíciles todo el tiempo, con métodos informados.
Los problemas del mundo real se entienden mejor con un ojo más científico y experimental. Se resuelven mejor desde una perspectiva de ingeniería. Inspiran la investigación teórica, y ocasionalmente son informados por ella. Como dijo Dijsktra, la informática (teórica) no se trata realmente de computadoras, ya no.
fuente