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 uniformemente distribuida . ^[1] Los 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 que puedan controlarse, calcularse o predecirse por completo, y que se puede establecer un límite inferior en su tasa de entropía. Para una fuente dada, 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 a partir de cualquier tipo de fuente débilmente aleatoria.

A veces, el término "sesgo" se utiliza para indicar la desviación de la uniformidad de una fuente débilmente aleatoria y, en la literatura más antigua, algunos extractores se denominan algoritmos de insesgo ^[2] , ya que toman la aleatoriedad de una fuente denominada "sesgada" y generan una distribución que parece insesgada. 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, al mismo tiempo que mantiene baja la longitud de la semilla. Intuitivamente, esto significa que se ha "extraído" de la fuente la mayor cantidad posible de aleatoriedad.

Un extractor tiene algunas similitudes conceptuales con un generador pseudoaleatorio (PRG), pero los dos conceptos no son idénticos. Ambos son funciones que toman como entrada una semilla pequeña y 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 uniforme. ^[3] ) Sin embargo, la definición general de PRG no especifica que se deba 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 solo se requiere que sea computacionalmente indistinguible de uniforme, un concepto algo más débil.

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 uno en el rango de . En esencia, esto mide qué tan probable es que tome su valor más probable, lo que da un límite en el peor de los casos sobre qué tan aleatorio parece. Si denotamos la distribución uniforme sobre , claramente . ${\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 mínima entropía 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 como salida una cadena de m bits. es un ( k ,  ε )-extractor , si para todas las distribuciones , la distribución de salida de es ε -cercana a . ${\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 un valor bajo (es decir, utilizar la menor aleatoriedad uniforme posible) y un valor tan alto como sea posible (es decir, obtener la mayor cantidad posible de bits de salida casi aleatorios). ${\displaystyle d}$ ${\displaystyle m}$

Extractores potentes

Un extractor es fuerte si la concatenación de la semilla con la salida del extractor produce una distribución que todavía está cerca de ser 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}\,}$

de modo que para cada distribución la distribución (las dos copias de denotan la misma variable aleatoria) es -cercana a 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 que existe un extractor. Se necesita una construcción explícita, que se da de la siguiente manera:

Definición (Extractor explícito): Para las 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 polinomial (en su longitud de entrada) y para cada n , Ext _n es un extractor ( k ( n ),  ε ( n )).

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)}$. ^[4]

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 . ^[5] A menudo es necesario generar claves secretas y aleatorias a partir de fuentes que son semisecretas o que pueden verse comprometidas hasta cierto punto. Al tomar una única clave aleatoria corta (y secreta) como fuente, 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 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 llama 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 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 manera adaptativa todos los bits 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 una función de recuperación adaptable cuya salida sea altamente aleatoria y uniformemente distribuida. Pero a menudo se necesita una condición más fuerte en la que cada salida ocurra con una probabilidad casi uniforme. Para este propósito se utilizan las funciones resilientes casi perfectas (APRF). La definición de una 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 ^[6] han demostrado un teorema que establece que si una función es una k -APRF, entonces también es una k -ERF. Más específicamente, cualquier extractor que tenga un error suficientemente pequeño y que tome como entrada una fuente de corrección de bits ajena a la función también es una APRF y, por lo tanto, también una 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 inconscientes, 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 es demostrado por Kamp y Zuckerman. ^[6] El lema se demuestra examinando la distancia desde el uniforme de la salida, que en un -extractor obviamente es como máximo , lo que satisface la condición de la 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 una k-APRF explícita , 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 despreciable): En la demostración de este teorema, necesitamos una definición de una función despreciable . Una función se define como despreciable si para todas las constantes . ${\displaystyle \epsilon (n)}$ ${\displaystyle \epsilon (n)=O\left({\frac {1}{n^{c}}}\right)}$ ${\displaystyle c}$

Prueba: considere el siguiente -extractor: La función es un extractor para el conjunto de fuentes de fijación de bits inconscientes: . 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ómputo lineal sobre 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 ya que es una función despreciable. ${\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, entonces el límite inferior de está dominado por . En el último paso, usamos el hecho de que lo que significa que la potencia de es como máximo . Y como es un 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 }}$

Con este valor de tenemos 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 de von Neumann

Tal vez el primer ejemplo se deba a John von Neumann . A partir del flujo de entrada, su extractor extraía bits, de dos en dos (primero y segundo, luego tercero y cuarto, y así sucesivamente). Si los dos bits coincidían, no se generaba ninguna salida. Si los bits diferían, se generaba el valor del primer bit. Se puede demostrar que el extractor de von Neumann produce una salida uniforme incluso si la distribución de 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. ^[7]

Por lo tanto, toma como entrada una secuencia de Bernoulli con p no necesariamente igual a 1/2, y genera como salida una secuencia de Bernoulli con De 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 ambos son igualmente probables. Para decirlo de manera simple, 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 sobre el extractor de Von Neumann incluyen el extractor Elias y Peres, el último de los cuales reutiliza bits para producir flujos de salida más grandes que el extractor de Von Neumann dado el mismo tamaño de flujo de entrada. ^[8]

Máquina del caos

Otro enfoque consiste en utilizar la salida de una máquina de caos aplicada al flujo de entrada. Este enfoque se basa generalmente 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 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, controlada mediante la especificación de tres parámetros: costo de tiempo , memoria requerida y clave secreta .

Cabe señalar que, si bien los sistemas caóticos verdaderos 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 implementan en computadoras digitales con representación numérica de precisión finita, como en las máquinas del caos que utilizan el sistema de punto flotante IEEE 754 , se ha demostrado que la periodicidad está muy por debajo del espacio completo para una longitud de bit dada. ^[9]

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 ]}

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 de salida de ellos, esa salida exhibirá entropía completa . ^[10]

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 tiempo de unidad de disco o retrasos del teclado, para producir un resultado uniformemente aleatorio.

Los extractores de aleatoriedad han desempeñado un papel importante en los recientes desarrollos de criptografía cuántica , por ejemplo, destilando la salida bruta de un generador de números aleatorios cuánticos en una salida más corta, segura y uniformemente aleatoria. ^[11]

La extracción de aleatoriedad también se utiliza en algunas ramas de la teoría de la complejidad computacional y en la construcción de códigos de corrección de errores decodificables por listas .

Véase también

• Decorrelación
• Generador de números aleatorios de hardware
• Fusión aleatoria
• Extractor difuso

Referencias

1. Extracción de aleatoriedad de distribuciones muestreables. Portal.acm.org. 12 de noviembre de 2000. p. 32. ISBN 9780769508504. Recuperado el 12 de junio de 2012 .
2. David K. Gifford, Números aleatorios naturales, MIT /LCS/TM-371, Instituto Tecnológico de Massachusetts, agosto de 1988.
3. Luca Trevisan. "Extractores y generadores pseudoaleatorios" (PDF) . Consultado el 21 de octubre de 2013 .
4. Ronen Shaltiel. Desarrollos recientes en la construcción explícita de extractores. P. 5.
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.º 5, págs. 1231–1247.
6. Jesse Kamp y David Zuckerman. Extractores deterministas para fuentes con fijación de bits y criptografía resistente a la exposición. P. 1242.
7. John von Neumann. Diversas técnicas utilizadas en relación con los dígitos aleatorios. Applied Math Series, 12:36–38, 1951.
8. Prasitsupparote, Amonrat; Konno, Norio; Shikata, Junji (octubre de 2018). "Análisis numérico y no asintótico de los 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. 
9. Persohn, Kyle; Povinelli, Richard. "Análisis de generadores de números pseudoaleatorios de mapas logísticos para la periodicidad inducida por la representación de punto flotante de precisión finita". Universidad Marquette . Consultado el 3 de enero de 2024 .
10. 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
11. Ma, Xiongfeng; Xu, Feihu; Xu, He; Tan, Xiaoqing; Qi, Bing; Lo, Hoi-Kwong (junio de 2013). "Posprocesamiento para generadores cuánticos de números aleatorios: evaluación de entropía y extracción de aleatoriedad". Physical Review A . 87 (6). arXiv : 1207.1473 . doi :10.1103/PhysRevA.87.062327.

• 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 optimalidad de la estrategia avanzada de múltiples niveles) (notas de la clase), Michael Mitzenmacher