Leftover hash-lemma

From Wikipedia, the free encyclopedia

You have new messages (last change).

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help improve the introduction to meet Wikipedia's layout standards. 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"