Leftover hash-lemma

From Wikipedia, the free encyclopedia

 The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.

The leftover hash-lemma was first stated by Russell Impagliazzo, Leonid Levin and Michael Luby and is a very useful tool in cryptography.[citation needed] It tells us that we can extract about H_\infty(X) (the min-entropy of X) bits from a random variable X that are almost uniformly distributed. In other words, an adversary who has some partial knowledge about X, will have almost no knowledge about the extracted value. That is why this is also called privacy amplification (see privacy amplification section in Quantum Crytography).

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

[edit] Leftover hash-lemma

Let X be a random variable over \mathcal X and let m > 0. Let h : \mathcal{S} \times \mathcal{X} \rightarrow \{0,1\}^m be a 2-universal hash function. If

m \leq H_\infty(X) - 2 \log(1/\varepsilon),

then for S uniform over \mathcal S and independent of X, we have

\delta((h(S,X),S),(U,S)) \leq \varepsilon,

where U is uniform over {0,1}m and independent of S.

\delta(X,Y) = \frac 1 2 \sum_v \left | \Pr[X=v] - \Pr[Y=v] \right | is the statistical distance between X and Y.

[edit] See also

[edit] References