Leftover hash lemma

Short description: Lemma in cryptography

This article needs editing for compliance with Wikipedia's Manual of Style. In particular, it has problems with use of second person; see MOS:YOU. Please help improve it if you can. (February 2023) (Learn how and when to remove this template message)

|

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

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

More precisely, the leftover hash lemma states that it is possible to extract a length asymptotic to H∞(X) (the min-entropy of X) bits from a random variable X) that are almost uniformly distributed.[clarification needed] In other words, an adversary who has some partial knowledge about X, 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 X be a random variable over 𝒳 and let m>0. Let h:𝒮×𝒳->{0,1}m be a 2-universal hash function. If

m≤H∞(X)−2log⁡(1ε)

then for S uniform over 𝒮 and independent of X, we have:

δ[(h(S,X),S),(U,S)]≤ε.

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

H∞(X)=−log⁡maxxPr⁡[X=x] is the min-entropy of X, which measures the amount of randomness X has. The min-entropy is always less than or equal to the Shannon entropy. Note that maxxPr⁡[X=x] is the probability of correctly guessing X. (The best guess is to guess the most probable value.) Therefore, the min-entropy measures how difficult it is to guess X.

0≤δ(X,Y)=12∑v|Pr⁡[X=v]−Pr⁡[Y=v]|≤1 is a statistical distance between X and Y.

## See also

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

## References

1. ↑ Johnson, David S., ed. (1989), "Pseudo-random Generation from one-way functions", Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, {ACM}, pp. 12–24, doi:10.1145/73007.73009
2. ↑ "Lecture 22: The Leftover Hash Lemma and Explicit Extractions", Lecture notes for MIT course 6.842, Randomness and Computation (MIT), April 30, 2008, https://people.csail.mit.edu/ronitt/COURSE/S08/drafts/22.pdf, retrieved 2019-02-19

* 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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Leftover hash lemma. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Leftover_hash_lemma&oldid=4299773"