Leftover hash-lemma
Encyclopedia
The leftover hash lemma is a lemma
in cryptography
first stated by Russell Impagliazzo
, Leonid Levin
, and Michael Luby
.
Imagine that you have a secret key
that has 
uniform random bit
s, and you would like to use this secret key to encrypt a message. Unfortunately, you were a bit careless with the key, and know that an adversary
was able to learn about
bits of that key, but you do not know which. Can you still use your key, or do you have to throw it away and choose a new key? The leftover hash lemma tells us that we can produce a key of almost
bits, over which the adversary has almost no knowledge. Since the adversary knows all but 
bits, this is almost optimal.
More precisely, the leftover hash lemma tells us that we can extract about
(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. That is why this is also called privacy amplification (see privacy amplification section in the article Quantum key distribution).
Randomness extractor
s achieve the same result, but use (normally) less randomness.
be a random variable over 
and let 
. Let 
be a 2-universal
hash function
. If
then for
uniform over 
and independent of 
, we have
where
is uniform over 
and independent of 
.
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 
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
.
is a statistical distance
between
and 
.
Lemma (mathematics)
In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than as a statement in-and-of itself...
in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
first stated by Russell Impagliazzo
Russell Impagliazzo
Russell Impagliazzo is a professor of computer science at the University of California, San Diego. He received his doctorate from the University of California, Berkeley. His advisor was Manuel Blum. He spent two years as a postdoc at the University of Toronto. He is a 2004 Guggenheim fellow...
, Leonid Levin
Leonid Levin
-External links:* at Boston University....
, and Michael Luby
Michael Luby
Michael George Luby is a mathematician and computer scientist, VP Technology at Qualcomm and former co-founder and Chief Technology Officer of Digital Fountain. In coding theory he is known for leading the invention of the Tornado codes and the LT codes...
.
Imagine that you have a secret key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
that has uniform random bitBit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s, and you would like to use this secret key to encrypt a message. Unfortunately, you were a bit careless with the key, and know that an adversary
Adversary (cryptography)
In cryptography, an adversary is a malicious entity whose aim is to prevent the users of the cryptosystem from achieving their goal...
was able to learn about
bits of that key, but you do not know which. Can you still use your key, or do you have to throw it away and choose a new key? The leftover hash lemma tells us that we can produce a key of almostAlmost all
In mathematics, the phrase "almost all" has a number of specialised uses."Almost all" is sometimes used synonymously with "all but finitely many" or "all but a countable set" ; see almost....
bits, over which the adversary has almost no knowledge. Since the adversary knows all but bits, this is almost optimal.More precisely, the leftover hash lemma tells us that we can extract about
(the min-entropyMin-entropy
In probability theory or information theory, the min-entropy of a discrete random event x with possible states 1... n and corresponding probabilities p1... pn is...
of
) bits from a random variableRandom variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
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. That is why this is also called privacy amplification (see privacy amplification section in the article Quantum key distribution).Randomness extractor
Randomness extractor
A randomness extractor, often simply called "an extractor," is a function which, when applied to a high-entropy source , generates a random output that is shorter, but uniformly distributed...
s achieve the same result, but use (normally) less randomness.
Leftover hash lemma
Let be a random variable over and let . Let be a 2-universalUniversal hashing
Using universal hashing refers to selecting a hash function at random from a family of hash functions with a certain mathematical property . This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary...
hash function
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
. If
then for
uniform over and independent of , we havewhere
is uniform over and independent of . is the Min-entropyMin-entropy
In probability theory or information theory, the min-entropy of a discrete random event x with possible states 1... n and corresponding probabilities p1... pn is...
of
, which measures the amount of randomness has. The min-entropy is always less than or equal to the Shannon entropy. Note that is the probability of correctly guessing . (The best guess is to guess the most probable value.) Therefore, the min-entropymeasures how difficult it is to guess
. is a statistical distanceStatistical distance
In statistics, probability theory, and information theory, a statistical distance quantifies the distance between two statistical objects, which can be two samples, two random variables, or two probability distributions, for example.-Metrics:...
between
and .See also
- Universal hashingUniversal hashingUsing universal hashing refers to selecting a hash function at random from a family of hash functions with a certain mathematical property . This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary...
- Min-entropyMin-entropyIn probability theory or information theory, the min-entropy of a discrete random event x with possible states 1... n and corresponding probabilities p1... pn is...
- Rényi entropyRényi entropyIn information theory, the Rényi entropy, a generalisation of Shannon entropy, is one of a family of functionals for quantifying the diversity, uncertainty or randomness of a system...
- Information theoretic securityInformation theoretic securityA cryptosystem is information-theoretically secure if its security derives purely from information theory. That is, it is secure even when the adversary has unlimited computing power. The adversary simply does not have enough information to break the security...