Lema hash sobrante

Lema en criptografía

El lema hash sobrante es un lema en criptografía formulado por primera vez por Russell Impagliazzo , Leonid Levin y Michael Luby . ^[1]

Dada una clave secreta $X$ que tiene $n$ bits aleatorios uniformes , de los cuales un adversario pudo conocer los valores de algunos $t$ $<$ $n$ bits de esa clave, el lema hash restante establece que es posible producir una clave de aproximadamente $n$ $-$ $t$ bits, sobre los cuales el adversario casi no tiene conocimiento, sin saber cuáles $t$ son conocidos por el adversario. Dado que el adversario conoce todos los bits excepto $n$ $-$ $t$ , esto es casi óptimo .

Más precisamente, el lema del hash restante establece que es posible extraer una longitud asintótica a (la entropía mínima de $X$ ) bits de una variable aleatoria $X$ ) que están distribuidos casi uniformemente. En otras palabras, un adversario que tiene algún conocimiento parcial sobre $X$ , casi no tendrá conocimiento sobre el valor extraído. Esto también se conoce como amplificación de la privacidad (ver la sección de amplificación de la privacidad en el artículo Distribución de claves cuánticas ). $H_{\infty}(X)$

Los extractores de aleatoriedad logran el mismo resultado, pero utilizan (normalmente) menos aleatoriedad.

Sea $X$ una variable aleatoria sobre y sea . Sea una función hash 2-universal . Si ${\mathcal {X}}$ $m>0$ ${\textstyle h\colon {\mathcal {S}}\times {\mathcal {X}}\rightarrow \{0,\,1\}^{m}}$

{\textstyle m\leq H_{\infty }(X)-2\log \left({\frac {1}{\varepsilon }}\right)}

Entonces, para $S$ uniforme e independiente de $X$ , tenemos: ${\mathcal {S}}$

{\textstyle \delta \left[(h(S,X),S),(U,S)\right]\leq \varepsilon .}

donde $U$ es uniforme e independiente de $S.$ ^[2 ] $\{0,1\}^{m}$

${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ es la min-entropía de $X$ , que mide la cantidad de aleatoriedad que tiene $X$ . La min-entropía siempre es menor o igual que la entropía de Shannon . Nótese que es la probabilidad de adivinar correctamente $X$ . (La mejor suposición es adivinar el valor más probable). Por lo tanto, la min-entropía mide qué tan difícil es adivinar $X$ . ${\textstyle \max _{x}\Pr[X=x]}$

${\textstyle 0\leq \delta (X,Y)={\frac {1}{2}}\sum _{v}\left|\Pr[X=v]-\Pr[Y=v]\right|\leq 1}$ es una distancia estadística entre $X$ e $Y.$

Véase también

Referencias

^ Impagliazzo, Russell ; Levin, Leonid A. ; Luby, Michael (1989), "Generación pseudoaleatoria a partir de funciones unidireccionales", en Johnson, David S. (ed.), Actas del 21.º Simposio anual de la ACM sobre teoría de la computación, 14-17 de mayo de 1989, Seattle, Washington, EE. UU. , {ACM}, págs. 12-24, doi :10.1145/73007.73009, S2CID 18587852
^ Rubinfeld, Ronnit ; Drucker, Andy (30 de abril de 2008), "Conferencia 22: El lema hash restante y las extracciones explícitas" (PDF) , Notas de clase para el curso MIT 6.842, Aleatoriedad y computación , MIT , consultado el 19 de febrero de 2019

CH Bennett, G. Brassard y JM Robert. Amplificación de la privacidad mediante debate público. SIAM Journal on Computing, 17(2):210-229, 1988.
C. Bennett, G. Brassard, C. Crepeau y U. Maurer. Amplificación generalizada de la privacidad. IEEE Transactions on Information Theory, 41, 1995.
J. Håstad, R. Impagliazzo, LA Levin y M. Luby. Un generador pseudoaleatorio a partir de cualquier función unidireccional. SIAM Journal on Computing, v28 n4, págs. 1364-1396, 1999.

[1] Impagliazzo, Russell ; Levin, Leonid A. ; Luby, Michael (1989), "Generación pseudoaleatoria a partir de funciones unidireccionales", en Johnson, David S. (ed.), Actas del 21.º Simposio anual de la ACM sobre teoría de la computación, 14-17 de mayo de 1989, Seattle, Washington, EE. UU. , {ACM}, págs. 12-24, doi :10.1145/73007.73009, S2CID 18587852

[2] Rubinfeld, Ronnit ; Drucker, Andy (30 de abril de 2008), "Conferencia 22: El lema hash restante y las extracciones explícitas" (PDF) , Notas de clase para el curso MIT 6.842, Aleatoriedad y computación , MIT , consultado el 19 de febrero de 2019