Leftover hash lemma

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

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

The leftover hash lemma is a lemma in cryptography first stated by Russell Impagliazzo, Leonid Levin, and Michael Luby. Given a secret key that has uniform random bits, of which an adversary was able to learn the values of some bits of that key, the leftover hash lemma states that it is possible to produce a key of about bits, over which the adversary has almost no knowledge, without knowing which are known to the adversary.

Since the adversary knows all but bits, this is almost optimal. More precisely, the leftover hash lemma states that it is possible to extract a length asymptotic to H_\infty(X) (the min-entropy of ) bits from a random variable ) that are almost uniformly distributed.

In other words, an adversary who has some partial knowledge about , 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). In quantum cryptographic settings, privacy amplification must also bound information held in a quantum system.

Hayashi analyzed the exponential decreasing rate of leaked information for universal random privacy amplification, giving exponent bounds for universal hashing against quantum side information. Randomness extractors achieve the same result, but use (normally) less randomness. Let be a random variable over \mathcal{X} and let m > 0 .…

The leftover hash lemma is a lemma in cryptography first stated by Russell Impagliazzo, Leonid Levin, and Michael Luby. Given a secret key that has uniform random bits, of which an adversary was able to learn the values of some bits of that key, the leftover hash lemma states that it is possible to produce a key of about bits, over which the adversary has almost no knowledge, without knowing which are known to the adversary.

Since the adversary knows all but bits, this is almost optimal. More precisely, the leftover hash lemma states that it is possible to extract a length asymptotic to H_\infty(X) (the min-entropy of ) bits from a random variable ) that are almost uniformly distributed.

In other words, an adversary who has some partial knowledge about , 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). In quantum cryptographic settings, privacy amplification must also bound information held in a quantum system.

Hayashi analyzed the exponential decreasing rate of leaked information for universal random privacy amplification, giving exponent bounds for universal hashing against quantum side information. Randomness extractors achieve the same result, but use (normally) less randomness. Let be a random variable over \mathcal{X} and let m > 0 .

Let h\colon \mathcal{S} \times \mathcal{X} \rightarrow \{0,\, 1\}^m be a 2-universal hash function. If m \leq H_\infty(X) - 2 \log\left(\frac{1}{\varepsilon}\right) then for uniform over \mathcal{S} and independent of , we have: \delta\left[(h(S, X), S), (U, S)\right] \leq \varepsilon. where is uniform over \{0, 1\}^m and independent of .

H_\infty(X) = -\log \max_x \Pr[X=x] is the min-entropy of , which measures the amount of randomness has. The min-entropy is always less than or equal to the Shannon entropy. Note that \max_x \Pr[X=x] is the probability of correctly guessing .

(The best guess is to guess the most probable value.) Therefore, the min-entropy measures how difficult it is to guess . 0 \le \delta(X, Y) = \frac{1}{2} \sum_v \left| \Pr[X=v] - \Pr[Y=v] \right| \le 1 is a statistical distance between and .

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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1349883748 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.