Leftover hash-lemma

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help Wikipedia by improving the introduction according to the guidelines laid out at Wikipedia:Guide to layout. You can discuss the issue on the talk page.

The leftover hash-lemma was first stated by Russell Impagliazzo, Leonid Levin and Michael Luby and is a very useful tool in cryptography. 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.

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

C. H. Bennett, G. Brassard, and J. M. Robert. Privacy amplification by public discussion. SIAM Journal on Computing, 17(2):210-229, 1988.

R. Impagliazzo, L. A. Levin, and M. Luby. Pseudo-random generation from one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC '89)}, pages 12-24. ACM Press, 1989.

C. Bennett, G. Brassard, C. Crepeau, and U. Maurer. Generalized privacy amplification. IEEE Transactions on Information Theory, 41, 1995.

J. Hastad, 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.

Retrieved from "http://en.wikipedia.org../../../l/e/f/Leftover_hash-lemma.html"

Categories: Wikipedia articles needing context | Theory of cryptography | Statistical lemmas | Probability theory