Leftover Hash Lemma
Let 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 .
Read more about this topic: Leftover Hash Lemma
Famous quotes containing the word leftover:
“To brew up an adult, it seems that some leftover childhood must be mixed in; a little unfinished business from the past periodically intrudes on our adult life, confusing our relationships and disturbing our sense of self.”
—Roger Gould (20th century)