Lema hash sobrante

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

Imagina que tienes una clave secreta $X$ que tiene $n$ bits aleatorios uniformes y te gustaría usar esta clave secreta para cifrar un mensaje. Desafortunadamente, fuiste un poco descuidado con la clave y sabes que un adversario pudo aprender los valores de algunos $t$ $<$ $n$ bits de esa clave, pero no sabes cuáles $t$ bits. ¿Puedes seguir usando tu clave o tienes que tirarla y elegir una nueva? El lema hash restante nos dice que podemos producir una clave de aproximadamente $n$ $-$ $t$ bits, sobre la cual el adversario casi no tiene conocimiento. Dado que el adversario conoce todos los bits excepto $n$ $-$ $t$ , esto es casi óptimo .

Más precisamente, el lema hash restante nos dice que podemos extraer una longitud asintótica a (la min-entropía 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. Es por eso que esto también se llama amplificación de privacidad (ver la sección de amplificación de privacidad en el artículo Distribución de clave cuántica ). $Estilo de visualización 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.