extractor difuso

La predictibilidad indica la probabilidad de que un adversario pueda adivinar una clave secreta. Matemáticamente hablando, la predictibilidad de una variable aleatoria${\displaystyle A}$es${\displaystyle \max _{\mathrm {a} }P[A=a]}$.

Por ejemplo, dado un par de variables aleatorias${\displaystyle A}$y${\displaystyle B}$, si el adversario sabe${\displaystyle b}$de${\displaystyle B}$, entonces la previsibilidad de${\displaystyle A}$será${\displaystyle \max _{\mathrm {a} }P[A=a|B=b]}$Por lo tanto, un adversario puede predecir${\displaystyle A}$con ${\displaystyle E_{b\leftarrow B}[\max _{\mathrm {a} }P[A=a|B=b]]}$. Usamos el promedio sobre${\displaystyle B}$ya que no está bajo control del adversario, sino desde que se sabe${\displaystyle b}$hace la predicción de${\displaystyle A}$adversarial, tomamos el peor caso${\displaystyle A}$.

La min-entropía indica la entropía en el peor de los casos. Matemáticamente hablando, se define como${\displaystyle H_{\infty }(A)=-\log(\max _{\mathrm {a} }P[A=a])}$.

Una variable aleatoria con una entropía mínima de al menos${\displaystyle m}$se llama un${\displaystyle m}$-fuente.

La distancia estadística es una medida de distinguibilidad. Matemáticamente hablando, se expresa para dos distribuciones de probabilidad.${\displaystyle A}$y${\displaystyle B}$como${\displaystyle SD[A,B]}$=${\displaystyle {\frac {1}{2}}\sum _{\mathrm {v} }|P[A=v]-P[B=v]|}$. En cualquier sistema, si${\displaystyle A}$es reemplazado por${\displaystyle B}$, se comportará como el sistema original con una probabilidad de al menos${\displaystyle 1-SD[A,B]}$.

Configuración${\displaystyle M}$como un extractor de aleatoriedad fuerte . La función aleatoria Ext: ${\displaystyle M\rightarrow \{0,1\}^{l}}$, con aleatoriedad de longitud${\displaystyle r}$, es un${\displaystyle (m,l,\epsilon )}$Extractor potente para todos${\displaystyle m}$-fuentes${\displaystyle W}$en${\displaystyle M(\operatorname {Ext} (W;I),I)\approx _{\epsilon }(U_{l},U_{r}),}$dónde${\displaystyle I=U_{r}}$es independiente de${\displaystyle W}$.

La salida del extractor es una clave generada a partir de${\displaystyle w\leftarrow W}$con la semilla${\displaystyle i\leftarrow I}$. Se comporta independientemente de otras partes del sistema, con la probabilidad de${\displaystyle 1-\epsilon }$Los extractores potentes pueden extraer como máximo${\displaystyle l=m-2\log {\frac {1}{\epsilon }}+O(1)}$bits de un arbitrario${\displaystyle m}$-fuente.

El boceto seguro permite reconstruir la entrada ruidosa; de modo que, si la entrada es${\displaystyle w}$y el boceto es${\displaystyle s}$, dado${\displaystyle s}$y un valor${\displaystyle w'}$cerca de${\displaystyle w}$,${\displaystyle w}$Se puede recuperar. Pero el boceto${\displaystyle s}$no debe revelar información sobre${\displaystyle w}$, para mantenerlo seguro.

Si${\displaystyle \mathbb {M} }$es un espacio métrico , un boceto seguro recupera el punto${\displaystyle w\in \mathbb {M} }$desde cualquier punto${\displaystyle w'\in \mathbb {M} }$cerca de${\displaystyle w}$, sin revelar${\displaystyle w}$sí mismo.

Un${\displaystyle (m,{\tilde {m}},t)}$El método de boceto seguro consiste en un par de procedimientos aleatorios eficientes (SS – Boceto; Rec – Recuperación) tales que:

(1) El procedimiento de esbozado SS toma como entrada${\displaystyle w\in \mathbb {M} }$y devuelve una cadena${\displaystyle s\in {\{0,1\}^{*}}}$.

El procedimiento de recuperación Rec toma como entrada los dos elementos.${\displaystyle w'\in \mathbb {M} }$y${\displaystyle s\in {\{0,1\}^{*}}}$.

(2) Corrección: Si ${\displaystyle dis(w,w')\leq t}$entonces${\displaystyle Rec(w',SS(w))=w}$.

(3) Seguridad: Para cualquier${\displaystyle m}$-fuente terminada${\displaystyle M}$, la min-entropía de${\displaystyle W}$, dado${\displaystyle s}$, es alto:

Para cualquier${\displaystyle (W,E)}$, si${\displaystyle {\tilde {H}}_{\mathrm {\infty } }(W|E)\geq m}$, entonces${\displaystyle {\tilde {H}}_{\mathrm {\infty } }(W|SS(W),E)\geq {\tilde {m}}}$.

Los extractores difusos no recuperan la entrada original, sino que generan una cadena.${\displaystyle R}$(que es casi uniforme) de${\displaystyle w}$y permitir su reproducción posterior (usando una cadena auxiliar)${\displaystyle P}$) dado cualquier${\displaystyle w'}$cerca de${\displaystyle w}$. Los extractores fuertes son un caso especial de extractores difusos cuando${\displaystyle t}$= 0 y${\displaystyle P=I}$.

Un${\displaystyle (m,l,t,\epsilon )}$El extractor difuso es un par de procedimientos aleatorios eficientes (Gen – Generar y Rep – Reproducir) tales que:

(1) Gen, dado${\displaystyle w\in \mathbb {M} }$, genera una cadena extraída${\displaystyle R\in {\mathbb {\{} 0,1\}^{l}}}$y una cadena auxiliar${\displaystyle P\in {\mathbb {\{} 0,1\}^{*}}}$.

(2) Corrección: Si${\displaystyle dis(w,w')\leq t}$y${\displaystyle (R,P)\leftarrow Gen(w)}$, entonces${\displaystyle Rep(w',P)=R}$.

(3) Seguridad: Para todas las fuentes m${\displaystyle W}$encima${\displaystyle M}$, la cadena${\displaystyle R}$es casi uniforme, incluso dado${\displaystyle P}$Entonces, cuando ${\displaystyle {\tilde {H}}_{\mathrm {\infty } }(W|E)\geq m}$, entonces${\displaystyle (R,P,E)\approx (U_{\mathrm {l} },P,E)}$.

Por lo tanto, los extractores difusos generan secuencias aleatorias de bits casi uniformes, lo cual es un requisito previo para el uso de aplicaciones criptográficas (como claves secretas). Dado que los bits de salida no son uniformes, existe el riesgo de una menor seguridad; pero la distancia a una distribución uniforme no es mayor que${\displaystyle \epsilon }$Mientras esta distancia sea suficientemente pequeña, la seguridad seguirá siendo adecuada.

Los bocetos seguros se pueden utilizar para construir extractores difusos: por ejemplo, aplicando SS a${\displaystyle w}$para obtener${\displaystyle s}$y un extractor fuerte Ext, con aleatoriedad${\displaystyle x}$, a${\displaystyle w}$, Llegar${\displaystyle R}$.${\displaystyle (s,x)}$se puede almacenar como cadena auxiliar${\displaystyle P}$.${\displaystyle R}$puede ser reproducido por${\displaystyle w'}$y${\displaystyle P=(s,x)}$.${\displaystyle Rec(w',s)}$puede recuperarse${\displaystyle w}$y${\displaystyle Ext(w,x)}$puede reproducirse${\displaystyle R}$.

El siguiente lema formaliza esto.

Supongamos que (SS,Rec) es un${\displaystyle (M,m,{\tilde {m}},t)}$boceto seguro y sea Ext un caso promedio${\displaystyle (n,{\tilde {m}},l,\epsilon )}$extractor fuerte. Entonces lo siguiente (Gen, Rep) es un${\displaystyle (M,m,l,t,\epsilon )}$extractor difuso:

(1) Gen${\displaystyle (w,r,x)}$: colocar${\displaystyle P=(SS(w;r),x),R=Ext(w;x),}$y salida${\displaystyle (R,P)}$.

(2) Rep${\displaystyle (w',(s,x))}$: recuperar${\displaystyle w=Rec(w',s)}$y salida${\displaystyle R=Ext(w;x)}$.

Prueba:

de la definición de boceto seguro (Definición 2),${\displaystyle H_{\infty }(W|SS(W))\geq {\tilde {m}}}$;

y dado que Ext es un caso promedio${\displaystyle (n,m,l,\epsilon )}$-extractor potente;

${\displaystyle SD((Ext(W;X),SS(W),X),(U_{l},SS(W),X))=SD((R,P),(U_{l},P))\leq \epsilon .}$

Si (SS,Rec) es un ${\displaystyle (M,m,{\tilde {m}},t)}$boceto seguro y Ext es un${\displaystyle (n,{\tilde {m}}-log({\frac {1}{\delta }}),l,\epsilon )}$extractor fuerte, entonces la construcción anterior (Gen, Rep) es una    ${\displaystyle (M,m,l,t,\epsilon +\delta )}$extractor difuso.

El artículo citado incluye muchos límites combinatorios genéricos sobre bocetos seguros y extractores difusos. ^{[ 2 ]}

Cuando no existe riesgo de que los datos se borren y solo de que se corrompan, la mejor medida para usar para la corrección de errores es la distancia de Hamming. Hay dos construcciones comunes para corregir errores de Hamming, dependiendo de si el código es lineal o no. Ambas construcciones comienzan con un código de corrección de errores que tiene una distancia de${\displaystyle 2t+1}$dónde${\displaystyle {t}}$es el número de errores tolerados.

Cuando se trabaja con un alfabeto muy grande o cadenas muy largas, se obtiene un universo muy grande.${\displaystyle {\mathcal {U}}}$, puede ser más eficiente tratar${\displaystyle w}$y${\displaystyle w'}$como conjuntos y observar las diferencias entre conjuntos para corregir errores. Para trabajar con un conjunto grande${\displaystyle w}$Es útil observar su vector característico.${\displaystyle x_{w}}$, que es un vector binario de longitud${\displaystyle n}$que tiene un valor de 1 cuando un elemento${\displaystyle a\in {\mathcal {U}}}$y${\displaystyle a\in w}$o 0 cuando${\displaystyle a\notin w}$. La mejor manera de reducir el tamaño de un boceto seguro cuando${\displaystyle n}$es grande es para hacer${\displaystyle k}$grande, ya que el tamaño está determinado por${\displaystyle n-k}$Un buen código sobre el cual basar esta construcción es un${\displaystyle [n,n-t\alpha ,2t+1]_{2}}$Código BCH , donde${\displaystyle n=2^{\alpha }-1}$y${\displaystyle t\ll n}$, de modo que${\displaystyle k\leq n-log{n \choose {t}}}$Resulta útil que los códigos BCH puedan decodificarse en tiempo sublineal.

Cuando los datos pueden corromperse o eliminarse, la mejor medida a utilizar es la distancia de edición . Para crear una construcción basada en la distancia de edición, la forma más sencilla es comenzar con una construcción para la diferencia de conjuntos o la distancia de Hamming como paso de corrección intermedio, y luego construir la construcción de la distancia de edición a partir de esta.

Existen muchos otros tipos de errores y distancias que pueden utilizarse para modelar otras situaciones. La mayoría de estas construcciones posibles se basan en construcciones más sencillas, como las construcciones de distancia de edición.

Para este modelo más restrictivo, utilice un BSC.${\displaystyle _{p}}$para crear un${\displaystyle w'}$con una probabilidad${\displaystyle p}$en cada posición en${\displaystyle w'}$que el bit recibido es incorrecto. Este modelo puede demostrar que la pérdida de entropía se limita a${\displaystyle nH(p)-o(n)}$, dónde${\displaystyle H}$es la función de entropía binaria . Si min-entropía${\displaystyle m\geq n(H({\frac {1}{2}}-\gamma ))+\varepsilon }$entonces${\displaystyle n({\frac {1}{2}}-\gamma )}$Se pueden tolerar errores, por alguna razón constante.${\displaystyle \gamma >0}$.

Para este modelo, los errores no tienen una distribución conocida y pueden provenir de un adversario, siendo las únicas restricciones las siguientes:${\displaystyle dis_{\text{err}}\leq t}$y que una palabra corrupta depende únicamente de la entrada.${\displaystyle w}$y no en el boceto seguro. Se puede demostrar para este modelo de error que nunca habrá más de${\displaystyle t}$errores, ya que este modelo puede explicar todos los procesos de ruido complejos, lo que significa que se puede alcanzar el límite de Shannon; para ello se antepone una permutación aleatoria al esquema seguro que reducirá la pérdida de entropía.

Este modelo difiere del modelo dependiente de la entrada al tener errores que dependen tanto de la entrada${\displaystyle w}$y el boceto seguro, y un adversario está limitado a algoritmos de tiempo polinomial para introducir errores. Dado que los algoritmos que pueden ejecutarse en un tiempo mejor que polinomial no son factibles actualmente en el mundo real, entonces un resultado positivo utilizando este modelo de error garantizaría que cualquier error pueda corregirse. Este es el modelo menos restrictivo, donde la única forma conocida de aproximarse al límite de Shannon es usar códigos decodificables por lista , aunque esto puede no ser siempre útil en la práctica, ya que devolver una lista, en lugar de una sola palabra clave, puede no ser siempre aceptable.

Idealmente, la cadena auxiliar${\displaystyle P}$no revelaría ninguna información sobre la entrada biométrica${\displaystyle w}$Esto solo es posible cuando cada lectura biométrica posterior${\displaystyle w'}$es idéntico al original${\displaystyle w}$En este caso, en realidad no hay necesidad de la cadena auxiliar; por lo tanto, es fácil generar una cadena que no esté correlacionada de ninguna manera con${\displaystyle w}$.

Dado que es deseable aceptar datos biométricos${\displaystyle w'}$similar a${\displaystyle w}$, la cadena auxiliar${\displaystyle P}$deben estar correlacionados de alguna manera. Cuanto más diferentes${\displaystyle w}$y${\displaystyle w'}$cuanto más se permita, mayor será la correlación entre${\displaystyle P}$y${\displaystyle w}$; cuanto más correlacionados estén, más información${\displaystyle P}$revela sobre${\displaystyle w}$Podemos considerar esta información como una función.${\displaystyle f(W)}$La mejor solución posible es asegurarse de que un adversario no pueda obtener información útil de la cadena de ayuda.

Un mapa probabilístico${\displaystyle Y()}$oculta los resultados de funciones con una pequeña cantidad de fugas${\displaystyle \epsilon }$La fuga es la diferencia en la probabilidad que tienen dos adversarios de adivinar alguna función, cuando uno conoce el mapa probabilístico y el otro no. Formalmente:

${\displaystyle |\Pr[A_{1}(Y(W))=f(W)]-\Pr[A_{2}()=f(W)]|\leq \epsilon }$

Si la función${\displaystyle \operatorname {Gen} (W)}$es un mapa probabilístico, entonces incluso si un adversario conoce ambas cadenas auxiliares${\displaystyle P}$y la cadena secreta${\displaystyle R}$, tienen una probabilidad insignificantemente mayor de descubrir algo sobre el tema que si no supieran nada. La cadena${\displaystyle R}$Se supone que debe mantenerse en secreto; por lo tanto, incluso si se filtra (lo cual debería ser muy improbable), el adversario aún no puede averiguar nada útil sobre el tema, siempre y cuando${\displaystyle \epsilon }$es pequeño. Podemos considerar${\displaystyle f(W)}$que exista alguna correlación entre la entrada biométrica y alguna característica física de la persona. Configuración${\displaystyle Y=\operatorname {Gen} (W)=R,P}$En la ecuación anterior, se transforma en:

${\displaystyle |\Pr[A_{1}(R,P)=f(W)]-\Pr[A_{2}()=f(W)]|\leq \epsilon }$

Esto significa que si un adversario${\displaystyle A_{1}}$tiene${\displaystyle (R,P)}$y un segundo adversario${\displaystyle A_{2}}$no sabe nada, sus mejores conjeturas en${\displaystyle f(W)}$son solo${\displaystyle \epsilon }$aparte.

Los extractores difusos uniformes son un caso especial de extractores difusos, donde la salida${\displaystyle (R,P)}$de${\displaystyle Gen(W)}$es insignificante en comparación con las cadenas seleccionadas de la distribución uniforme, es decir${\displaystyle (R,P)\approx _{\epsilon }(U_{\ell },U_{|P|})}$.

Dado que los bocetos seguros implican extractores difusos, la construcción de un boceto seguro uniforme permite la fácil construcción de un extractor difuso uniforme. En un boceto seguro uniforme, el procedimiento del boceto${\displaystyle SS(w)}$es un extractor de aleatoriedad${\displaystyle Ext(w;i)}$, dónde${\displaystyle w}$es la entrada biométrica y${\displaystyle i}$es la semilla aleatoria . Dado que los extractores de aleatoriedad generan una cadena que parece provenir de una distribución uniforme, ocultan toda la información sobre su entrada.

Los bocetos del extractor se pueden utilizar para construir${\displaystyle (m,t,\epsilon )}$-Funciones hash unidireccionales perfectamente difusas. Cuando se utiliza como función hash, la entrada${\displaystyle w}$es el objeto que desea hashear. El${\displaystyle P,R}$eso${\displaystyle Gen(w)}$La salida es el valor hash. Si uno quisiera verificar que un${\displaystyle w'}$dentro${\displaystyle t}$del original${\displaystyle w}$ellos verificarían que${\displaystyle Rep(w',P)=R}$. Dichas funciones hash unidireccionales perfectas difusas son funciones hash especiales donde aceptan cualquier entrada con como máximo${\displaystyle t}$errores, en comparación con las funciones hash tradicionales que solo aceptan cuando la entrada coincide exactamente con la original. Las funciones hash criptográficas tradicionales intentan garantizar que es computacionalmente inviable encontrar dos entradas diferentes que produzcan el mismo valor hash. Las funciones hash difusas perfectamente unidireccionales hacen una afirmación análoga. Hacen que sea computacionalmente inviable encontrar dos entradas que sean más que${\displaystyle t}$Distancia de Hamming separada y hash al mismo valor.

Un método para construir extractores difusos robustos es utilizar funciones hash . Esta construcción requiere dos funciones hash.${\displaystyle H_{1}}$y${\displaystyle H_{2}}$. El${\displaystyle Gen(W)}$La función produce la cadena auxiliar.${\displaystyle P}$adjuntando la salida de un boceto seguro.${\displaystyle s=SS(w)}$al hash de ambas lecturas${\displaystyle w}$y boceto seguro${\displaystyle s}$Genera la cadena secreta${\displaystyle R}$aplicando la segunda función hash a${\displaystyle w}$y${\displaystyle s}$Formalmente:

${\displaystyle Gen(w):s=SS(w),return:P=(s,H_{1}(w,s)),R=H_{2}(w,s)}$

La función de reproducción${\displaystyle Rep(W,P)}$También hace uso de las funciones hash.${\displaystyle H_{1}}$y${\displaystyle H_{2}}$Además de verificar que la entrada biométrica sea lo suficientemente similar a la recuperada mediante el${\displaystyle Rec(W,S)}$función, también verifica que el hash en la segunda parte de${\displaystyle P}$en realidad se derivó de${\displaystyle w}$y${\displaystyle s}$. Si se cumplen ambas condiciones, devuelve${\displaystyle R}$, que a su vez es la segunda función hash aplicada a${\displaystyle w}$y${\displaystyle s}$Formalmente:

${\displaystyle Rep(w',{\tilde {P}}):}$Conseguir${\displaystyle {\tilde {s}}}$y${\displaystyle {\tilde {h}}}$de${\displaystyle {\tilde {P}};{\tilde {w}}=Rec(w',{\tilde {s}}).}$ Si${\displaystyle \Delta ({\tilde {w}},w')\leq t}$y${\displaystyle {\tilde {h}}=H_{1}({\tilde {w}},{\tilde {s}})}$entonces${\displaystyle return:H_{2}({\tilde {w}},{\tilde {s}})}$demás${\displaystyle return:fail}$

Si${\displaystyle P}$Ha sido manipulado, será obvio, porque${\displaystyle Rep}$fallará en la salida con una probabilidad muy alta. Para hacer que el algoritmo acepte una diferente${\displaystyle P}$, un adversario tendría que encontrar un${\displaystyle {\tilde {w}}}$de tal manera que${\displaystyle H_{1}(w,s)=H_{1}({\tilde {w}},{\tilde {s}})}$Dado que se cree que las funciones hash son funciones unidireccionales , es computacionalmente inviable encontrar tal${\displaystyle {\tilde {w}}}$. Vidente${\displaystyle P}$no proporcionaría a un adversario ninguna información útil. Dado que, nuevamente, las funciones hash son funciones unidireccionales, es computacionalmente inviable para un adversario invertir la función hash y averiguar${\displaystyle w}$. Parte de${\displaystyle P}$es el boceto seguro, pero por definición el boceto revela información insignificante sobre su entrada. De manera similar, al ver${\displaystyle R}$(aunque nunca debería verlo) no proporcionaría a un adversario ninguna información útil, ya que un adversario no podría revertir la función hash y ver la entrada biométrica.