Un extractor de aleatoriedad , a menudo llamado simplemente "extractor", es una función que, al aplicarse a la salida de una fuente de entropía débilmente aleatoria , junto con una semilla corta y uniformemente aleatoria, genera una salida altamente aleatoria que parece independiente de la fuente y uniformemente. distribuido . [1] Entre los ejemplos de fuentes débilmente aleatorias se incluyen la desintegración radiactiva o el ruido térmico.; la única restricción sobre las posibles fuentes es que no hay forma de que se puedan controlar, calcular o predecir por completo, y que se puede establecer un límite inferior en su tasa de entropía. Para una fuente determinada, un extractor de aleatoriedad puede incluso considerarse un verdadero generador de números aleatorios ( TRNG ); pero no hay un solo extractor que haya demostrado producir una salida verdaderamente aleatoria de cualquier tipo de fuente débilmente aleatoria.
A veces, el término "sesgo" se utiliza para denotar la desviación de una fuente débilmente aleatoria de la uniformidad, y en la literatura más antigua, algunos extractores se denominan algoritmos no sesgados , [2] ya que toman la aleatoriedad de una fuente llamada "sesgada" y generan un distribución que parece no sesgada. La fuente débilmente aleatoria siempre será más larga que la salida del extractor, pero un extractor eficiente es aquel que reduce esta proporción de longitudes tanto como sea posible, mientras que simultáneamente mantiene baja la longitud de la semilla. Intuitivamente, esto significa que se ha "extraído" de la fuente tanta aleatoriedad como sea posible.
Tenga en cuenta que un extractor tiene algunas similitudes conceptuales con un generador pseudoaleatorio (PRG), pero los dos conceptos no son idénticos. Ambas son funciones que toman como entrada una semilla pequeña, uniformemente aleatoria y producen una salida más larga que "parece" uniformemente aleatoria. Algunos generadores pseudoaleatorios son, de hecho, también extractores. (Cuando un PRG se basa en la existencia de predicados de núcleo duro , se puede pensar en la fuente débilmente aleatoria como un conjunto de tablas de verdad de dichos predicados y demostrar que la salida es estadísticamente cercana a la uniforme. [3] ) Sin embargo, el La definición general de PRG no especifica que se deba usar una fuente débilmente aleatoria, y mientras que en el caso de un extractor, la salida debe ser estadísticamente cercana a la uniforme, en un PRG solo se requiere que sea computacionalmente indistinguible de uniforme, un poco más débil. concepto.
La Publicación Especial NIST 800-90B (borrador) recomienda varios extractores, incluida la familia de hash SHA, y establece que si la cantidad de entrada de entropía es el doble de la cantidad de bits de salida de ellos, esa salida puede considerarse esencialmente completamente aleatoria. [4]
Definición formal de extractores
La minientropía de una distribución (denotado ), es el mayor número real tal que para cada en el rango de . En esencia, esto mide la probabilidad de es tomar su valor más probable, dando un límite en el peor de los casos sobre cuán aleatorio aparece. Dejando denotar la distribución uniforme sobre , claramente .
Para una distribución de n bitscon min-entropía k , decimos que es un distribución.
Definición (Extractor): ( k , ε ) -extractor
Dejar ser una función que toma como entrada una muestra de un distribución y una semilla de d- bit dey genera una cadena de m bits.es un ( k , ε ) -extractor , si para todos distribuciones , la distribución de salida de es ε -cerca de.
En la definición anterior, ε -close se refiere a la distancia estadística .
Intuitivamente, un extractor toma una entrada de n bits débilmente aleatoria y una semilla corta y uniformemente aleatoria y produce una salida de m bits que parece uniformemente aleatoria. El objetivo es tener un bajo (es decir, utilizar la menor aleatoriedad uniforme posible) y un como sea posible (es decir, para obtener tantos bits de salida casi aleatorios como podamos).
Extractores fuertes
Un extractor es fuerte si al concatenar la semilla con la producción del extractor se obtiene una distribución que todavía es casi uniforme.
Definición (Extractor fuerte): A-extractor fuerte es una función
tal que por cada distribución la distribución (las dos copias de denotar la misma variable aleatoria) es -cerca de la distribución uniforme en .
Extractores explícitos
Utilizando el método probabilístico , se puede demostrar que existe un ( k , ε ) -extractor, es decir, que la construcción es posible. Sin embargo, normalmente no basta con demostrar que existe un extractor. Se necesita una construcción explícita, que se da de la siguiente manera:
Definición (Extractor explícito): Para funciones k ( n ), ε ( n ), d ( n ), m ( n ) una familia Ext = {Ext n } de funciones
es un extractor explícito ( k , ε ), si Ext ( x , y ) se puede calcular en tiempo polinomial (en su longitud de entrada) y para cada n , Ext n es a ( k ( n ), ε ( n )) -extractor.
Por el método probabilístico, se puede demostrar que existe un ( k , ε ) -extractor con longitud de semilla
y longitud de salida
- . [5]
Dispersores
Una variante del extractor de aleatoriedad con propiedades más débiles es el dispersor .
Extractores de aleatoriedad en criptografía
Uno de los aspectos más importantes de la criptografía es la generación de claves aleatorias . [6] A menudo es necesario generar claves secretas y aleatorias a partir de fuentes que son semisecretas o que pueden estar comprometidas hasta cierto punto. Al tomar una clave aleatoria única, corta (y secreta) como fuente, se puede usar un extractor para generar una clave pseudoaleatoria más larga, que luego se puede usar para el cifrado de clave pública. Más específicamente, cuando se usa un extractor fuerte, su salida parecerá uniformemente aleatoria, incluso para alguien que vea parte (pero no toda) de la fuente. Por ejemplo, si se conoce la fuente pero no se conoce la semilla (o viceversa). Esta propiedad de los extractores es particularmente útil en lo que comúnmente se denomina criptografía resistente a la exposición en la que el extractor deseado se utiliza como una función resistente a la exposición (ERF). La criptografía resistente a la exposición tiene en cuenta que el hecho de que es difícil mantener en secreto el intercambio inicial de datos que a menudo tiene lugar durante la inicialización de una aplicación de cifrado , por ejemplo, el remitente de información cifrada tiene que proporcionar a los receptores la información necesaria. para el descifrado.
Los siguientes párrafos definen y establecen una relación importante entre dos tipos de ERF, k -ERF y k -APRF, que son útiles en la criptografía resistente a la exposición.
Definición ( k -ERF): Un k-ERF adaptativo es una función donde, para una entrada aleatoria , cuando un adversario computacionalmente ilimitado puede leer de forma adaptativa todos los excepto por bits por alguna función insignificante (definido a continuación).
El objetivo es construir un ERF adaptativo cuya salida sea altamente aleatoria y distribuida uniformemente. Pero a menudo se necesita una condición más fuerte en la que cada salida se produzca con una probabilidad casi uniforme. Para este propósito, se utilizan funciones resilientes casi perfectas (APRF). La definición de APRF es la siguiente:
Definición (k-APRF): A APRF es una función donde, para cualquier entorno de bits de la entrada a cualquier valor fijo, el vector de probabilidad de la salida sobre las elecciones aleatorias para el los bits restantes satisface para todos y por alguna función insignificante .
Kamp y Zuckerman [7] han demostrado un teorema que establece que si una funciónes un k -APRF, entoncestambién es un k -ERF. Más específicamente, cualquier extractor que tenga un error suficientemente pequeño y que tome como entrada una fuente de fijación de bits ajena es también un APRF y, por lo tanto, también un k -ERF. Un extractor más específico se expresa en este lema:
Lema: Cualquiera -extractor para el conjunto de fuentes de reparación de bits ajenas, donde es insignificante, también es un k-APRF.
Kamp y Zuckerman prueban este lema. [7] El lema se prueba examinando la distancia del uniforme de la salida, que en un-extractor obviamente es como máximo , que cumple la condición de la APRF.
El lema conduce al siguiente teorema, que indica que, de hecho, existe una función k -APRF como se describe:
Teorema (existencia): Para cualquier constante positiva , existe un k-APRF explícito , calculable en un número lineal de operaciones aritméticas en -cadenas de bits, con y .
Definición (función despreciable): En la demostración de este teorema, necesitamos una definición de función despreciable . Una función se define como insignificante si para todas las constantes .
Prueba: considere lo siguiente-extractor: La función es un extractor para el conjunto de fuente de reparación de bits ajena: . posee , y .
La prueba de la existencia de este extractor con , así como el hecho de que es computable en tiempo de computación lineal en la longitud de se puede encontrar en el artículo de Jesse Kamp y David Zuckerman (p. 1240).
Que este extractor cumple los criterios del lema es trivialmente cierto como es una función insignificante.
La talla de es:
Desde que sabemos luego el límite inferior en está dominado por . En el último paso usamos el hecho de que lo que significa que el poder de es como máximo . Y desde es un entero positivo sabemos que es como máximo .
El valor de se calcula utilizando la definición del extractor, donde sabemos:
y usando el valor de tenemos:
Usando este valor de damos cuenta del peor de los casos, donde está en su límite inferior. Ahora, mediante cálculos algebraicos, obtenemos:
Que insertado en el valor de da
- ,
lo que prueba que existe un extractor k-APRF explícito con las propiedades dadas.
Ejemplos de
Extractor Von Neumann
Quizás el ejemplo más antiguo se deba a John von Neumann . Del flujo de entrada, su extractor tomó bits, dos a la vez (primero y segundo, luego tercero y cuarto, y así sucesivamente). Si los dos bits coincidían, no se generaba salida. Si los bits diferían, se emitía el valor del primer bit. Se puede demostrar que el extractor de Von Neumann produce una salida uniforme incluso si la distribución de los bits de entrada no es uniforme siempre que cada bit tenga la misma probabilidad de ser uno y no haya correlación entre los bits sucesivos. [8]
Por lo tanto, toma como entrada una secuencia de Bernoulli con p no necesariamente igual a 1/2, y genera una secuencia de Bernoulli conDe manera más general, se aplica a cualquier secuencia intercambiable ; solo se basa en el hecho de que para cualquier par, 01 y 10 son igualmente probables: para ensayos independientes, estos tienen probabilidades, mientras que para una secuencia intercambiable la probabilidad puede ser más complicada, pero ambas son igualmente probables.
Máquina del caos
Otro enfoque es utilizar la salida de una máquina del caos aplicada al flujo de entrada. Este enfoque generalmente se basa en las propiedades de los sistemas caóticos . Los bits de entrada se envían a la máquina, evolucionando órbitas y trayectorias en múltiples sistemas dinámicos. Por tanto, pequeñas diferencias en la entrada producen salidas muy diferentes. Una máquina de este tipo tiene una salida uniforme incluso si la distribución de bits de entrada no es uniforme o tiene fallas graves y, por lo tanto, puede utilizar fuentes de entropía débiles . Además, este esquema permite una mayor complejidad, calidad y seguridad del flujo de salida, controlado mediante la especificación de tres parámetros: costo de tiempo , memoria requerida y clave secreta .
Función hash criptográfica
También es posible utilizar una función hash criptográfica como extractor de aleatoriedad. Sin embargo, no todos los algoritmos hash son adecuados para este propósito. [ cita requerida ]
Aplicaciones
Los extractores de aleatoriedad se utilizan ampliamente en aplicaciones criptográficas, en las que se aplica una función hash criptográfica a una fuente de alta entropía, pero no uniforme, como información de temporización de la unidad de disco o retrasos del teclado, para producir un resultado uniformemente aleatorio.
Los extractores de aleatoriedad han jugado un papel en los desarrollos recientes en criptografía cuántica , donde el extractor de aleatoriedad utiliza fotones para generar bits aleatorios seguros. [1]
La extracción aleatoria también se utiliza en algunas ramas de la teoría de la complejidad computacional .
La extracción aleatoria también se utiliza para convertir datos en una muestra aleatoria simple, que se distribuye normalmente e independiente, que es deseada por las estadísticas.
Ver también
Referencias
- ^ "Extracción de la aleatoriedad de distribuciones muestrables" . Portal.acm.org . Consultado el 12 de junio de 2012 .
- ^ David K. Gifford, Números aleatorios naturales, MIT / LCS / TM-371, Instituto de Tecnología de Massachusetts, agosto de 1988.
- ^ Luca Trevisan. "Extractores y generadores pseudoaleatorios" (PDF) . Consultado el 21 de octubre de 2013 .
- ^ Recomendación para las fuentes de entropía utilizadas para la generación aleatoria de bits (borrador) NIST SP800-90B , Barker y Kelsey, agosto de 2012, sección 6.4.2
- ^ Ronen Shaltiel. Desarrollos recientes en la construcción explícita de extractores. P. 5.
- ^ Jesse Kamp y David Zuckerman. Extractores deterministas para fuentes de fijación de bits y criptografía resistente a la exposición., SIAM J. Comput., Vol. 36, núm. 5, págs. 1231-1247.
- ^ a b Jesse Kamp y David Zuckerman. Extractores deterministas para fuentes de fijación de bits y criptografía resistente a la exposición. P. 1242.
- ^ John von Neumann. Varias técnicas utilizadas en relación con dígitos aleatorios. Serie de matemáticas aplicadas, 12: 36–38, 1951.
- Extractores de aleatoriedad para fuentes y aplicaciones independientes , Anup Rao
- Desarrollos recientes en construcciones explícitas de extractores , Ronen Shaltiel
- Extracción aleatoria y derivación de claves utilizando los modos CBC, Cascade y HMAC , Yevgeniy Dodis et al.
- Derivación clave y extracción aleatoria , Olivier Chevassut et al.
- Extractores deterministas para fuentes de fijación de bits y criptografía resistente a la exposición , Jesse Kamp y David Zuckerman
- Lanzar una moneda sesgada (y la optimización de la estrategia avanzada de varios niveles) (notas de la conferencia) , Michael Mitzenmacher