Leftover hash lemma

Leftover Hash Lemma (LHL), also known as the Leftover Hash Lemma, is a fundamental concept in cryptography and theoretical computer science. It provides a formal foundation for the security of various cryptographic constructs, particularly those involving hash functions. The lemma essentially states that, given a hash function with certain properties, the output of the function can be made arbitrarily close to a uniform distribution over its output space, even if the input distribution is not uniform, provided that the output length is sufficiently shorter than the input length.

Overview

The Leftover Hash Lemma is crucial in understanding how randomness can be "extracted" from a non-uniform distribution using a hash function. This is particularly important in cryptographic applications where randomness is a key component of security protocols, such as in the generation of cryptographic keys or in the process of cryptographic hashing. The lemma guarantees that, under certain conditions, the output of a hash function can be nearly indistinguishable from a truly random sequence of bits, thereby ensuring a high level of security.

Formal Definition

Let H be a family of hash functions mapping n-bit strings to m-bit strings. The Leftover Hash Lemma states that for any distribution X over n-bit strings with min-entropy k, and for any ε > 0, if m < k - 2log(1/ε), then the statistical distance between the distribution of H(X) and the uniform distribution over m-bit strings is at most ε. Here, H(X) denotes the distribution obtained by applying a randomly chosen hash function from H to X.

Applications

The Leftover Hash Lemma has numerous applications in cryptography and information theory. Some of the most notable applications include:

• Key Derivation Functions (KDFs): In cryptographic protocols, KDFs are used to derive one or more secret keys from a secret value. The LHL can be used to prove the security of KDFs that rely on hash functions to produce keys that are close to uniformly random.
• Randomness Extraction: The lemma is fundamental in the construction of randomness extractors, which are algorithms designed to generate a nearly uniform random output from a weakly random source.
• Privacy Amplification: In quantum cryptography, particularly in Quantum Key Distribution (QKD) protocols, the LHL is used in the privacy amplification step to ensure that the final shared key is secure against an eavesdropper, even if they have partial knowledge of the key.

Limitations

While the Leftover Hash Lemma provides a powerful tool for achieving cryptographic security, it also has limitations. The requirement for the hash function family to behave like a random oracle is significant; in practice, constructing such a family can be challenging. Additionally, the lemma does not address the computational aspects of generating the hash function or the input distribution, which can be critical in practical applications.

See Also

• Hash function
• Cryptography
• Uniform distribution (discrete)
• Min-entropy
• Randomness extractor