Leftover hash lemma

The leftover hash lemma is a lemma in cryptography first stated by Russell Impagliazzo, Leonid Levin, and Michael Luby.

Given a secret key Template:Mvar that has Template:Mvar uniform random bits, of which an adversary was able to learn the values of some Template:Math bits of that key, the leftover hash lemma states that it is possible to produce a key of about Template:Math bits, over which the adversary has almost no knowledge, without knowing which Template:Math are known to the adversary. Since the adversary knows all but Template:Math bits, this is almost optimal.

More precisely, the leftover hash lemma states that it is possible to extract a length asymptotic to $H_{\mathrm{\infty }}(X)$ (the min-entropy of Template:Mvar) bits from a random variable Template:Mvar) that are almost uniformly distributed. In other words, an adversary who has some partial knowledge about Template:Mvar, will have almost no knowledge about the extracted value. This is also known as privacy amplification (see privacy amplification section in the article Quantum key distribution).

Randomness extractors achieve the same result, but use (normally) less randomness.

Let Template:Mvar be a random variable over $𝒳$ and let $m>0$. Let $h:𝒮\times 𝒳\to \{0,1{\}}^m$ be a 2-universal hash function. If

$m\le H_{\mathrm{\infty }}(X)-2\log \left(\frac{1}{\epsilon }\right)$

then for Template:Mvar uniform over $𝒮$ and independent of Template:Mvar, we have:

$\delta [(h(S,X),S),(U,S)]\le \epsilon .$

where Template:Mvar is uniform over $\{0,1{\}}^m$ and independent of Template:Mvar.

$H_{\mathrm{\infty }}(X)=-\log \underset{x}{\max }\mathrm{Pr}[X=x]$ is the min-entropy of Template:Mvar, which measures the amount of randomness Template:Mvar has. The min-entropy is always less than or equal to the Shannon entropy. Note that $\underset{x}{\max }\mathrm{Pr}[X=x]$ is the probability of correctly guessing Template:Mvar. (The best guess is to guess the most probable value.) Therefore, the min-entropy measures how difficult it is to guess Template:Mvar.

$0\le \delta (X,Y)=\frac{1}{2}\sum _v|\mathrm{Pr}[X=v]-\mathrm{Pr}[Y=v]|\le 1$ is a statistical distance between Template:Mvar and Template:Mvar.

See also

• Universal hashing
• Min-entropy
• Rényi entropy
• Information-theoretic security

References

• C. H. Bennett, G. Brassard, and J. M. Robert. Privacy amplification by public discussion. SIAM Journal on Computing, 17(2):210-229, 1988.
• C. Bennett, G. Brassard, C. Crepeau, and U. Maurer. Generalized privacy amplification. IEEE Transactions on Information Theory, 41, 1995.
• J. Håstad, R. Impagliazzo, L. A. Levin and M. Luby. A Pseudorandom Generator from any One-way Function. SIAM Journal on Computing, v28 n4, pp. 1364-1396, 1999.