¿Ha habido investigaciones sobre la implementación de construcciones de extractor de aleatoriedad?
Parece que las pruebas de extractor utilizan Big-Oh, dejando la posibilidad de grandes constantes ocultas, lo que hace que las implementaciones programáticas sean potencialmente poco realistas.
Algún contexto: estoy interesado en usar extractores de aleatoriedad como una fuente rápida de (¿probablemente?) Números aleatorios para usar en simulaciones de Monte Carlo. Nosotros (un grupo de Física Computacional ETHZ) hemos sesgado las fuentes de alta entropía de generadores de números aleatorios cuánticos de los que nos gustaría extraer aleatoriedad. Un estudiante anterior intentó implementar una construcción de Trevisan y se topó con problemas de complejidad espacial. Aparte de ese estudiante, no he encontrado ninguna referencia a las personas que intentan implementar extractores.
Nota: Soy un estudiante de CS que es muy nuevo en el área de extractores de aleatoriedad y CS teóricos.
Respuestas:
Gran parte de la literatura sobre el extractor trata de minimizar la longitud de la semilla, lo cual es importante para la aplicación de la desaleatorización. Sin embargo, puede no ser crucial para los suyos. Además, a menudo la literatura se centra en un error relativamente grande (p. Ej., 1/100), lo cual está bien para la aleatorización pero puede ser problemático en otros entornos, que requieren un error exponencialmente pequeño.
En su entorno, puede estar bien generar de una vez por todas una semilla aleatoria larga (por ejemplo, arrojando monedas), y luego usarla para extraer. En este caso, podría usar funciones hash independientes por pares que tengan implementaciones bastante eficientes. Escribí un artículo con Shaltiel y Tromer sobre este tema. También puede usar funciones hash casi independientes, que pueden ser más eficientes y tener una semilla más pequeña. (No sé de antemano una buena referencia para su implementación eficiente, aunque ha habido varios trabajos al respecto).
Si tiene múltiples fuentes que son independientes , puede hacer mejores cosas. El extractor clásico de Hadamard funciona si la tasa de entropía es superior al 50% (esto debería mencionarse en las encuestas anteriores). Si la entropía es menor al 50%, entonces tuvimos una construcción simple con Impagliazzo y Wigderson . La dependencia entre el número de fuentes y el error alcanzado en la tasa de entropía no es ideal, aunque para comprenderlo realmente, deberá observar los límites exactos dados por los teoremas de productos de suma de última generación. (Y si está dispuesto a asumir ciertas conjeturas teóricas numéricas, puede obtener extractores aún más eficientes). Esta construcción se ha mejorado considerablemente de varias maneras, algunas de las cuales podrían ser relevantes para su aplicación.Tesis de Anup Rao .
fuente
En primer lugar, vea el tema relevante en Wikipedia. En segundo lugar, puede echar un vistazo al siguiente documento:
Desarrollos recientes en construcciones explícitas de extractores por Ronen Shaltiel.
El documento está escrito en forma de encuesta y puede ayudarlo a encontrar los "desarrollos recientes".
Finalmente, si todo lo que quiere es una secuencia de bits que "parezca" aleatoria (pero no necesariamente es criptográficamente segura), puede aplicar una función hash (como MD5 o SHA-1) a su fuente de alta entropía y obtener un Excelente resultado (para experimentos físicos) en muy poco tiempo.
fuente
También hay un buen artículo de Dodis, Gennaro, et al. que considera primitivas criptográficas prácticas que pueden usarse para extracción. Muestran que no se sabe que las funciones hash sean buenos extractores, sin embargo, un cifrado de bloque en modo CBC-MAC puede ser (con algunas letras pequeñas). También consideran las construcciones HMAC. El enfoque es atractivo para la implementación, ya que puede usar bibliotecas de criptografía estándar.
Para CBC-MAC, la "letra pequeña" es aproximadamente:
fuente
Para el caso del generador pseudoaleatorio criptográfico, también puede buscar HKDF . En el documento discuten extractores de aleatoriedad conceptual y prácticamente, y dan buenas referencias.
Como nota al margen para generar aleatoriedad para Monte Carlo, por supuesto, hay HAVEGE . Si su velocidad de bits y "capacidad de prueba" son suficientes, puede evitar tener que jugar con los generadores cuánticos.
fuente