Överblivet hash-lemma

Det överblivna hash-lemmat är ett lemma i kryptografi som först uttalades av Russell Impagliazzo , Leonid Levin och Michael Luby .

Föreställ dig att du har en hemlig nyckel $X$ som har $n$ enhetliga slumpmässiga bitar , och du skulle vilja använda denna hemliga nyckel för att kryptera ett meddelande. Tyvärr var du lite slarvig med nyckeln och vet att en motståndare kunde lära dig värdena för några $t < n$ bitar av den nyckeln, men du vet inte vilka $t$ bitar. Kan du fortfarande använda din nyckel, eller måste du slänga den och välja en ny nyckel? Det överblivna hash-lemmat säger oss att vi kan producera en nyckel på ungefär $n - t$ bitar, som motståndaren nästan inte känner till. Eftersom motståndaren kan alla utom $n - t$ bitar är detta nästan optimalt .

Mer exakt, det överblivna hash-lemmat berättar för oss att vi kan extrahera en asymptotisk längd till $H_{\infty }(X)$ ( minentropin för $X$ ) från en slumpvariabel $X$ som är nästan jämnt fördelade. Med andra ord, en motståndare som har viss delkunskap om $X$ , har nästan ingen kunskap om det utvunna värdet. Det är därför detta också kallas integritetsförstärkning (se avsnittet om integritetsförstärkning i artikeln Kvantnyckelfördelning ).

Slumpextraktorer uppnår samma resultat, men använder (normalt) mindre slumpmässighet.

Låt $X$ vara en slumpmässig variabel över ${\mathcal {X}}$ och låt $m>0$ . Låt ${\textstyle h\colon {\mathcal {S}}\times {\mathcal {X}}\rightarrow \{0,\,1\}^{m}}$ vara en 2-universell hashfunktion . Om

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

sedan för $S$ uniform över ${\mathcal {S}}$ och oberoende av $X$ , har vi:

{\textstil \delta \left[(h(S,X),S),(U,S)\höger]\leq \varepsilon .}

där $U$ är enhetlig över $\{0,1\}^{m}$ och oberoende av $S$ .

${\textstil H_{\infty }(X)=-\log \max _{x}\Pr[X=x]} är$ min- entropi av $X$ , som mäter mängden slumpmässighet $X$ har. Min-entropin är alltid mindre än eller lika med Shannon-entropin . Observera att ${\textstyle \max _{x}\Pr[X=x]}$ är sannolikheten att gissa $X korrekt$ . (Den bästa gissningen är att gissa det mest sannolika värdet.) Därför mäter minentropin hur svårt det är att gissa $X$ .

${\textstil 0\leq \delta (X,Y)={\frac {1}{2}}\summa _{v}\left|\Pr[X=v]-\Pr[Y=v] \right|\leq 1}$ är ett statistiskt avstånd mellan $X$ och $Y$ .

Se även