¿Existe alguna investigación actual sobre la implementación de extractores de aleatoriedad?

20

¿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.

Phillip Mates
fuente
También puede encontrar interesante la respuesta de arnab a mi pregunta: cstheory.stackexchange.com/questions/36/…
Suresh Venkat
Aquí hay una implementación de trabajo: wisdom.weizmann.ac.il/~neko/MAE-offline.html
Diego de Estrada

Respuestas:

19

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 .

Boaz Barak
fuente
Gracias por la respuesta / resumen bien escrito. He examinado el documento TRNG que escribiste con Shaltiel y Tromer. Se ve bastante prometedor. Me preguntaba si la página web del documento (y el código de implementación) está disponible en cualquier lugar ya que el enlace citado ( people.csail.mit.edu/tromer/trng ) en el documento no contiene ninguna información al respecto.
Phillip Mates
6

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.

MS Dousti
fuente
1
Gracias por la sugerencia hash y enlaces. En los enlaces no vi ninguna mención de personas que intentan implementar extractores. Tengo mucha curiosidad sobre si esto se está intentando. La mayoría de los documentos sobre extractores que he leído mencionan las aplicaciones prácticas de los extractores, pero no hacen referencia a ningún intento de implementación. Me dijeron que la razón por la que hemos evitado las funciones de hash es que no son probables al azar, lo cual es muy útil en el ámbito de las simulaciones de MC ya que los pseudo-RNG han demostrado, a veces, producir resultados inexactos [ref: prl. aps.org/abstract/PRL/v69/i23/p3382_1 ]
Phillip Mates el
4

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:

  • Asume que el blockcipher es una permutación psuedo-aleatoria
  • Debe tener una clave verdaderamente aleatoria (pero no necesariamente secreta) que pueda reutilizarse
  • Si la salida es m bits, la entrada debe tener al menos 2 m bits de entropía mínima
  • La longitud del bloque y la longitud de la clave deben ser las mismas (por lo tanto, si está utilizando AES, eso significa que solo AES-128 funciona)
  • La longitud de entrada está limitada pero el límite es alto
PulpSpy
fuente
3

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.

Desnudo
fuente