Extractor de aleatoriedad

Concepto de física

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ébil , junto con una semilla corta y uniformemente aleatoria, genera una salida altamente aleatoria que parece independiente de la fuente y distribuida uniformemente. . ^[1] Ejemplos de fuentes débilmente aleatorias incluyen la desintegración radiactiva o el ruido térmico ; la única restricción sobre las posibles fuentes es que no hay forma de controlarlas, calcularlas o predecirlas 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 existe ningún extractor que haya demostrado que produzca resultados verdaderamente aleatorios a partir de cualquier tipo de fuente débilmente aleatoria.

A veces, el término "sesgo" se utiliza para denotar la desviación de la uniformidad de una fuente débilmente aleatoria, y en la literatura más antigua, algunos extractores se denominan algoritmos insesgados , ^[2] ya que toman la aleatoriedad de una fuente denominada "sesgada" y generan una distribución que parece imparcial. La fuente débilmente aleatoria siempre será más larga que la salida del extractor, pero un extractor eficiente es aquel que reduce esta relación de longitudes tanto como sea posible, manteniendo al mismo tiempo la longitud de la semilla baja. Intuitivamente, esto significa que se ha "extraído" de la fuente la mayor cantidad de aleatoriedad posible.

Muchos generadores de números aleatorios de hardware tienen una o más "fuentes de ruido" que generan ruido de colores . El proceso de combinarlos y extraer bits aleatorios imparciales y no correlacionados (similar al ruido blanco ) a menudo se denomina blanqueamiento de software . ^{[3] [4] [5] [6]}

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 incondicionales , se puede pensar en la fuente débilmente aleatoria como un conjunto de tablas de verdad de dichos predicados y demostrar que el resultado es estadísticamente cercano a uniforme. ^[7] ) Sin embargo, el La definición general de PRG no especifica que se debe utilizar una fuente débilmente aleatoria, y mientras que en el caso de un extractor, la salida debe ser estadísticamente cercana a uniforme, en un PRG sólo se requiere que sea computacionalmente indistinguible de uniforme, una fuente algo más débil. concepto.

La publicación especial 800-90B (borrador) del NIST recomienda varios extractores, incluida la familia de hash SHA y establece que si la cantidad de entropía de entrada es el doble de la cantidad de bits que salen de ellos, esa salida exhibirá entropía completa . ^[8]

Definición formal de extractores.

La entropía mínima de una distribución (denotada como ) es el número real más grande tal que para cada en el rango de . En esencia, esto mide la probabilidad de que tome su valor más probable, dando un límite en el peor de los casos sobre cómo aparece el azar. Denotando claramente la distribución uniforme sobre . ${\displaystyle X}$ ${\displaystyle H_{\infty }(X)}$ ${\displaystyle k}$ ${\displaystyle \Pr[X=x]\leq 2^{-k}}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle U_{\ell }}$ ${\displaystyle \{0,1\}^{\ell }}$ ${\displaystyle H_{\infty }(U_{\ell })=\ell }$

Para una distribución de n bits con entropía mínima k , decimos que es una distribución. ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle (n,k)}$

Definición (Extractor): ( k ,  ε )-extractor

Sea una función que toma como entrada una muestra de una distribución y una semilla de d bits de y genera una cadena de m bits. es un extractor ( k ,  ε ) , si para todas las distribuciones , la distribución de salida de es ε -cerca de . ${\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\to \{0,1\}^{m}}$ ${\displaystyle (n,k)}$ ${\displaystyle X}$ ${\displaystyle U_{d}}$ ${\displaystyle {\text{Ext}}}$ ${\displaystyle (n,k)}$ ${\displaystyle X}$ ${\displaystyle {\text{Ext}}}$ ${\displaystyle U_{m}}$

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 una aleatoriedad baja (es decir, utilizar la menor aleatoriedad uniforme posible) y la más alta posible (es decir, obtener tantos bits de salida casi aleatorios como podamos). ${\displaystyle d}$ ${\displaystyle m}$

Extractores fuertes

Un extractor es fuerte si la concatenación de la semilla con la producción del extractor produce una distribución que aún es casi uniforme.

Definición (Extractor fuerte): Un extractor fuerte es una función ${\displaystyle (k,\epsilon )}$

${\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}\,}$

tal que para cada distribución la distribución (las dos copias de denotan la misma variable aleatoria) está cerca de la distribución uniforme en . ${\displaystyle (n,k)}$ ${\displaystyle X}$ ${\displaystyle U_{d}\circ {\text{Ext}}(X,U_{d})}$ ${\displaystyle U_{d}}$ ${\displaystyle \epsilon }$ ${\displaystyle U_{m+d}}$

Extractores explícitos

Utilizando el método probabilístico se puede demostrar que existe un extractor ( k ,  ε ), es decir, que la construcción es posible. Sin embargo, normalmente no basta con demostrar la existencia de 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

${\displaystyle {\text{Ext}}_{n}:\{0,1\}^{n}\times \{0,1\}^{d(n)}\rightarrow \{0,1\}^{m(n)}}$

es un extractor explícito ( k ,  ε ), si Ext( x ,  y ) se puede calcular en tiempo polinómico (en su longitud de entrada) y para cada n , Ext _n es a ( k ( n ),  ε ( n )) -extractor.

Mediante el método probabilístico, se puede demostrar que existe un extractor ( k ,  ε ) con longitud de semilla

${\displaystyle d=\log {(n-k)}+2\log \left({\frac {1}{\varepsilon }}\right)+O(1)}$

y longitud de salida

${\displaystyle m=k+d-2\log \left({\frac {1}{\varepsilon }}\right)-O(1)}$. ^[9]

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 . ^[10] 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 como fuente una clave aleatoria única, corta (y secreta), se puede utilizar un extractor para generar una clave pseudoaleatoria más larga, que luego se puede utilizar para el cifrado de clave pública. Más específicamente, cuando se utiliza un extractor potente, su salida parecerá uniformemente aleatoria, incluso para alguien que ve 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 llama criptografía resistente a la exposición , en la que el extractor deseado se utiliza como función resistente a la exposición (ERF). La criptografía resistente a la exposición tiene en cuenta 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 la información cifrada tiene que proporcionar a los receptores la información necesaria. para descifrar.

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 criptografía resistente a la exposición.

Definición ( k -ERF): Un k-ERF adaptativo es una función en la que, para una entrada aleatoria , cuando un adversario computacionalmente ilimitado puede leer de forma adaptativa todos excepto los bits, para alguna función insignificante (definida a continuación). ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle A}$ ${\displaystyle r}$ ${\displaystyle k}$ ${\displaystyle |\Pr\{A^{r}(f(r))=1\}-\Pr\{A^{r}(R)=1\}|\leq \epsilon (n)}$ ${\displaystyle \epsilon (n)}$

El objetivo es construir un ERF adaptativo cuya salida sea altamente aleatoria y esté distribuida uniformemente. Pero a menudo se necesita una condición más fuerte en la que cada producción ocurra con una probabilidad casi uniforme. Para ello se utilizan funciones resilientes casi perfectas (APRF). La definición de APRF es la siguiente:

Definición (k-APRF): Una APRF es una función donde, para cualquier configuración de bits de la entrada a cualquier valor fijo, el vector de probabilidad de la salida sobre las elecciones aleatorias para los bits restantes satisface para todos y para alguna función insignificante . ${\displaystyle k=k(n)}$ ${\displaystyle f}$ ${\displaystyle n-k}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle f(r)}$ ${\displaystyle k}$ ${\displaystyle |p_{i}-2^{-m}|<2^{-m}\epsilon (n)}$ ${\displaystyle i}$ ${\displaystyle \epsilon (n)}$

Kamp y Zuckerman ^[11] han demostrado un teorema que establece que si una función es k -APRF, entonces también es k -ERF. Más específicamente, cualquier extractor que tenga un error suficientemente pequeño y tome como entrada una fuente de fijación de bits ajena también es un APRF y, por lo tanto, también un k -ERF. Un extractor más específico se expresa en este lema: ${\displaystyle f}$ ${\displaystyle f}$

Lema: Cualquier extractor para el conjunto de fuentes de fijación de bits ajenas, donde es insignificante, también es un k-APRF. ${\displaystyle 2^{-m}\epsilon (n)}$ ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}$ ${\displaystyle (n,k)}$ ${\displaystyle \epsilon (n)}$

Este lema está demostrado por Kamp y Zuckerman. ^[11] El lema se prueba examinando la distancia desde el uniforme de la salida, que en un extractor obviamente es como máximo , lo que satisface la condición del APRF. ${\displaystyle 2^{-m}\epsilon (n)}$ ${\displaystyle 2^{-m}\epsilon (n)}$

El lema conduce al siguiente teorema, que establece que, de hecho, existe una función k -APRF como se describe:

Teorema (existencia): Para cualquier constante positiva , existe un k-APRF explícito , computable en un número lineal de operaciones aritméticas en cadenas de bits, con y . ${\displaystyle \gamma \leq {\frac {1}{2}}}$ ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}$ ${\displaystyle m}$ ${\displaystyle m=\Omega (n^{2\gamma })}$ ${\displaystyle k=n^{{\frac {1}{2}}+\gamma }}$

Definición (función insignificante): En la prueba de este teorema, necesitamos una definición de función insignificante . Una función se define como insignificante si para todas las constantes . ${\displaystyle \epsilon (n)}$ ${\displaystyle \epsilon (n)=O\left({\frac {1}{n^{c}}}\right)}$ ${\displaystyle c}$

Prueba: Considere lo siguiente -extractor: La función es un extractor para el conjunto de fuentes de fijación de bits ajenas: . tiene , y . ${\displaystyle \epsilon }$ ${\displaystyle f}$ ${\displaystyle (n,\delta n)}$ ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}$ ${\displaystyle f}$ ${\displaystyle m=\Omega (\delta ^{2}n)}$ ${\displaystyle \epsilon =2^{-cm}}$ ${\displaystyle c>1}$

La prueba de la existencia de este extractor con , así como el hecho de que es computable en tiempo de cálculo lineal en la longitud de se puede encontrar en el artículo de Jesse Kamp y David Zuckerman (p. 1240). ${\displaystyle \delta \leq 1}$ ${\displaystyle m}$

Que este extractor cumpla los criterios del lema es trivialmente cierto, al igual que una función insignificante. ${\displaystyle \epsilon =2^{-cm}}$

El tamaño de es: ${\displaystyle m}$

${\displaystyle m=\Omega (\delta ^{2}n)=\Omega (n)\geq \Omega (n^{2\gamma })}$

Como sabemos , el límite inferior está dominado por . En el último paso usamos el hecho de que significa que el poder de es como máximo . Y como es un número entero positivo sabemos que es como máximo . ${\displaystyle \delta \leq 1}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \gamma \leq {\frac {1}{2}}}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle n^{2\gamma }}$ ${\displaystyle n}$

El valor de se calcula utilizando la definición del extractor, donde sabemos: ${\displaystyle k}$

${\displaystyle (n,k)=(n,\delta n)\Rightarrow k=\delta n}$

y usando el valor de tenemos: ${\displaystyle m}$

${\displaystyle m=\delta ^{2}n=n^{2\gamma }}$

Usando este valor de tomamos en cuenta el peor caso, donde está en su límite inferior. Ahora mediante cálculos algebraicos obtenemos: ${\displaystyle m}$ ${\displaystyle k}$

${\displaystyle \delta ^{2}n=n^{2\gamma }}$

${\displaystyle \Rightarrow \delta ^{2}=n^{2\gamma -1}}$

${\displaystyle \Rightarrow \delta =n^{\gamma -{\frac {1}{2}}}}$

Que insertado en el valor de da. ${\displaystyle k}$

${\displaystyle k=\delta n=n^{\gamma -{\frac {1}{2}}}n=n^{\gamma +{\frac {1}{2}}}}$,

lo que demuestra que existe un extractor k-APRF explícito con las propiedades dadas. ${\displaystyle \Box }$

Ejemplos

Extractor von Neumann

Quizás el ejemplo más antiguo se deba a John von Neumann . Del flujo de entrada, su extractor tomó bits, de dos en dos (el primero y el segundo, luego el tercero y el cuarto, y así sucesivamente). Si los dos bits coincidían, no se generaba ninguna salida. Si los bits eran diferentes, 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 bits sucesivos. ^[12]

Por lo tanto, toma como entrada una secuencia de Bernoulli con p no necesariamente igual a 1/2, y genera una secuencia de Bernoulli con. Más generalmente, se aplica a cualquier secuencia intercambiable ; solo se basa en el hecho de que para cualquier par, 01 y 10 son igualmente probable: para ensayos independientes, estos tienen probabilidades , mientras que para una secuencia intercambiable la probabilidad puede ser más complicada, pero ambas son igualmente probables. En pocas palabras, debido a que los bits son estadísticamente independientes y debido a la propiedad conmutativa de la multiplicación, se seguiría que . Por lo tanto, si los pares de 01 y 10 se asignan a los bits 0 y 1 y se descartan los pares 00 y 11, entonces la salida será una distribución uniforme. ${\displaystyle p=1/2.}$ ${\displaystyle p\cdot (1-p)=(1-p)\cdot p}$ ${\displaystyle P(A\cap B)=P(A)P(B)=P(B)P(A)=P(B\cap A)}$

Las iteraciones del extractor de Von Neumann incluyen el extractor de Elias y Peres, el último de los cuales reutiliza bits para producir flujos de salida más grandes que el extractor de Von Neumann con el mismo tamaño de flujo de entrada. ^[13]

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 lo tanto, pequeñas diferencias en los insumos producen resultados muy diferentes. Una máquina de este tipo tiene una salida uniforme incluso si la distribución de los 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 especificando tres parámetros: costo de tiempo , memoria requerida y clave secreta .

Tenga en cuenta que si bien los verdaderos sistemas caóticos son matemáticamente sólidos para "amplificar" la entropía, esto se basa en la disponibilidad de números reales con una precisión infinita. Cuando se implementa en computadoras digitales con representación de números de precisión finita, como en máquinas del caos que utilizan punto flotante IEEE 754 , se ha demostrado que la periodicidad está muy por debajo del espacio completo para una longitud de bit determinada. ^[14]

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 fin. ^{[ cita necesaria ]}

Aplicaciones

Los extractores de aleatoriedad se utilizan ampliamente en aplicaciones criptográficas, mediante las cuales 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 aleatorio uniforme.

Los extractores de aleatoriedad han desempeñado un papel en los desarrollos recientes de la criptografía cuántica , donde el extractor de aleatoriedad utiliza fotones para generar bits aleatorios seguros.[1]

La extracción de aleatoriedad 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 y es independiente, como desean las estadísticas.

Ver también

• decorrelación
• Generador de números aleatorios de hardware
• Fusión de aleatoriedad
• extractor difuso

Referencias

1. Extracción de aleatoriedad de distribuciones muestrables. Portal.acm.org. 12 de noviembre de 2000. p. 32.ISBN​ 9780769508504. Consultado el 12 de junio de 2012 .
2. David K. Gifford, Números aleatorios naturales, MIT /LCS/TM-371, Instituto de Tecnología de Massachusetts, agosto de 1988.
3. "Estadística aplicada: prueba de números aleatorios". Troels C. Petersen.
4. "OneRNG: sobre la confianza y la desconfianza".
5. "John von Neumann".
6. Línea Graysen. "Métodos estadísticos no paramétricos utilizando R". 2019. pág. 24.
7. Luca Trevisan. "Extractores y generadores pseudoaleatorios" (PDF) . Consultado el 21 de octubre de 2013 .
8. 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
9. Ronen Shaltiel. Avances recientes en la construcción explícita de extractores. Pág. 5.
10. 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.
11. Jesse Kamp y David Zuckerman. Extractores deterministas para fuentes de fijación de bits y criptografía resistente a la exposición. Pág. 1242.
12. John von Neumann. Varias técnicas utilizadas en relación con dígitos aleatorios. Serie de matemáticas aplicadas, 12:36–38, 1951.
13. Prasitsupparote, Amonrat; Konno, Norio; Shikata, Junji (octubre de 2018). "Análisis numérico y no asintótico de extractores de Elias y Peres con secuencias de entrada finitas". Entropía . 20 (10): 729. Bibcode : 2018Entrp..20..729P. doi : 10.3390/e20100729 . ISSN  1099-4300. PMC 7512292 . PMID  33265818. 
14. Person, Kyle; Povinelli, Richard. "Análisis de generadores de números pseudoaleatorios de mapas logísticos para determinar la periodicidad inducida por representación de coma flotante de precisión finita". Universidad Marquette . Consultado el 3 de enero de 2024 .

• Extractores de aleatoriedad para fuentes y aplicaciones independientes, Anup Rao
• Desarrollos recientes en construcciones explícitas de extractores, Ronen Shaltiel
• Extracción de aleatoriedad y derivación de claves utilizando los modos CBC, Cascade y HMAC, Yevgeniy Dodis et al.
• Derivación de claves y extracción de aleatoriedad, 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 multinivel) (notas de clase), Michael Mitzenmacher