Extractor de aleatoriedad

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 ]} Ejemplos de fuentes débilmente aleatorias incluyen la desintegración radiactiva o el ruido térmico ; la única restricción en las posibles fuentes es que no hay forma de que puedan ser controladas, calculadas o predichas por completo, y que no 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 generador de números aleatorios verdaderos ( 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 denotar la desviación de una fuente débilmente aleatoria de la uniformidad, y en la literatura antigua, algunos extractores se denominan algoritmos de eliminación de sesgos , ^{[ 2 ]} ya que toman la aleatoriedad de una fuente supuestamente "sesgada" y generan una 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 relación de longitudes tanto como sea posible, manteniendo al mismo tiempo una longitud de semilla baja. Intuitivamente, esto significa que se ha "extraído" la mayor cantidad de aleatoriedad posible de la fuente.

Un extractor tiene algunas similitudes conceptuales con un generador pseudoaleatorio (GPA), pero ambos 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 GPA 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, la definición general de GPA 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 GPA solo se requiere que sea computacionalmente indistinguible de la uniforme, un concepto algo más débil.

La min-entropía de una distribución${\displaystyle X}$(denotado${\displaystyle H_{\infty}(X)}$), es el mayor número real${\displaystyle k}$de tal manera que${\displaystyle \Pr[X=x]\leq 2^{-k}}$por cada${\displaystyle x}$en el rango de${\displaystyle X}$En esencia, esto mide la probabilidad${\displaystyle X}$es tomar su valor más probable, dando un límite en el peor de los casos sobre cuán aleatorio es.${\displaystyle X}$aparece. Dejando${\displaystyle U_{\ell }}$denotamos la distribución uniforme sobre${\displaystyle \{{\texttt {0}},{\texttt {1}}\}^{\ell }}$, claramente ${\displaystyle H_{\infty }(U_{\ell })=\ell }$.

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

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

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

En la definición anterior, ε -cerca 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${\displaystyle d}$(es decir, utilizar la menor cantidad posible de aleatoriedad uniforme) y la mayor cantidad posible de${\displaystyle m}$lo más posible (es decir, obtener la mayor cantidad posible de bits de salida casi aleatorios).

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 semisecretas o que pueden estar comprometidas en cierta medida. Al tomar una única clave aleatoria 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 robusto, su salida parecerá uniformemente aleatoria, incluso para alguien que vea parte (pero no la totalidad) de la fuente. Por ejemplo, si se conoce la fuente pero no 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 usa como una función resistente a la exposición (ERF). La criptografía resistente a la exposición tiene en cuenta la dificultad de mantener en secreto el intercambio inicial de datos que suele tener 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 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${\displaystyle f}$donde, para una entrada aleatoria${\displaystyle r}$, cuando un adversario computacionalmente ilimitado${\displaystyle A}$puede leer de forma adaptativa todo${\displaystyle r}$excepto${\displaystyle k}$bits,${\displaystyle |\Pr\{A^{r}(f(r))=1\}-\Pr\{A^{r}(R)=1\}|\leq \epsilon (n)}$para alguna función insignificante${\displaystyle \epsilon (n)}$(definido a continuación).

El objetivo es construir una función de respuesta evolutiva adaptativa cuya salida sea altamente aleatoria y esté distribuida uniformemente. Sin embargo, a menudo se requiere una condición más estricta en la que cada salida ocurra con una probabilidad casi uniforme. Para ello, se utilizan funciones resilientes casi perfectas (APRF). La definición de una APRF es la siguiente:

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

Kamp y Zuckerman ^{[ 6 ]} han demostrado un teorema que establece que si una función${\displaystyle f}$es un k -APRF, entonces${\displaystyle f}$También es un k -ERF. Más específicamente, cualquier extractor con un error suficientemente pequeño que tome como entrada una fuente ciega y de corrección de bits 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: Cualquier${\displaystyle 2^{-m}\epsilon (n)}$-extractor${\displaystyle f:\{{\texttt {0}},{\texttt {1}}\}^{n}\rightarrow \{{\texttt {0}},{\texttt {1}}\}^{m}}$para el conjunto de${\displaystyle (n,k)}$fuentes de corrección de bits inconscientes, donde${\displaystyle \epsilon (n)}$es insignificante, también es un k-APRF.

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

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${\displaystyle \gamma \leq {\frac {1}{2}}}$Existe un k-APRF explícito.${\displaystyle f:\{{\texttt {0}},{\texttt {1}}\}^{n}\rightarrow \{{\texttt {0}},{\texttt {1}}\}^{m}}$, computable en un número lineal de operaciones aritméticas en${\displaystyle m}$cadenas de bits, con${\displaystyle m=\Omega (n^{2\gamma})}$y${\displaystyle k=n^{{\frac {1}{2}}+\gamma }}$.

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

Demostración: Consideremos lo siguiente${\displaystyle \epsilon }$-extractor: La función${\displaystyle f}$es un extractor para el conjunto de${\displaystyle (n,\delta n)}$Fuente de corrección de bits inconsciente:${\displaystyle f:\{{\texttt {0}},{\texttt {1}}\}^{n}\rightarrow \{{\texttt {0}},{\texttt {1}}\}^{m}}$.${\displaystyle f}$tiene${\displaystyle m=\Omega (\delta ^{2}n)}$,${\displaystyle \epsilon =2^{-cm}}$y${\displaystyle c>1}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

Que se insertó en el valor de${\displaystyle k}$da

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

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

Los extractores de aleatoriedad se utilizan ampliamente en aplicaciones criptográficas, donde 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 unidades de disco o retrasos del teclado, para obtener un resultado uniformemente aleatorio.

Los extractores de aleatoriedad han desempeñado un papel fundamental en los recientes avances de la criptografía cuántica , por ejemplo, al destilar la salida bruta de los generadores de números aleatorios cuánticos en una salida más corta, segura y uniformemente aleatoria. ^{[ 10 ]}

Los extractores robustos han demostrado ser útiles en la generación de números aleatorios verificables en sistemas comerciales. Recientemente, han permitido utilizar la aleatoriedad (casi perfecta) generada por una computadora cuántica para mejorar la calidad de la aleatoriedad en sistemas remotos que no tienen acceso a una computadora cuántica. ^{[ 11 ] [ 12 ] [ 13 ]} La capacidad de proporcionar aleatoriedad verificada mediante física cuántica completamente en software no sería posible sin el uso de extractores robustos. ^{[ 12 ]}

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 correctores de errores decodificables por lista .

• Decorrelación
• Generador de números aleatorios por hardware
• fusión aleatoria
• extractor difuso

• 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 correcció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 multinivel avanzada) (apuntes de clase) , Michael Mitzenmacher