# Why does entropy halve during its extraction?

It is common to use cryptographic hash functions to extract randomness from entropy sources. One of the quantitative criteria for this is that if 2n bits of entropy are put through a hash, n bits of uniformly distributed random numbers can be extracted.

Why is this? Where do the other n bits of entropy go? Perhaps naively, but if we adopt a water analogy, why can we only get 1 litre of water entropy out of a store that we've put 2 litres into? Is it possible to explain this without complex algebra? It seems counter intuitive that we can't get all the entropy out that was put into the hash function.

The scenario that vexes me is what if we chained hash functions for the hell of it. One cryptographic hash feeding the next. If we start at the top of the pile and input 16 bits of entropy, the available entropy would half passing through each hash. After passing through 5 hash functions, there would be <1 bit of entropy left. I can't fathom how that could be.

I can't find the original reference to n 2n, but there are many instances of this formula scattered throughout the literature. BUT. I have a counter example where this is not the case. The Quantis TRNG manages to output 75% of available entropy via matrix multiplication. And I think that I've seen this technique used in other TRNGs. It's simple compression of the raw entropy stream. Both hash functions and matrix multiplication is essentially similar, so what's going on?

Efficient constructions of generic (hence randomized) statistical extractors exist such as those built on the basis of universal hash functions . However, in spite of their simplicity, combinatorial and algebraic constructions present significant limitations for their practical use in generic KDF applications. For example, statistical extractors require a significant difference (called the gap) between the min-entropy $m$ of the source and the required number $m'$ of extracted bits (in particular, no statistical extractor can achieve a statistical distance, on arbitrary sources, better than $2^{−{m−m'\over 2}}$ [60, 63]). That is, one can use statistical extractors (with its provable properties) only when the min-entropy of the source is significantly higher than the length of output.
We note that random functions do not make by themselves good statistical extractors (here the key to the extractor is the description of the function itself). For example, if $\chi$ is the uniform distribution over $\{0, 1\}^{2k}$ (thus having min-entropy $2k$) and we choose a random function $f$ from $2k$ to $k$ bits, we expect $1/e^2$ of the points in $\{0, 1\}^k$ not to be in the image of $f$ (i.e., they are assigned probability 0 regardless of the sample from $\chi$), thus inducing an output distribution that is statistically far from uniform. Furthermore, the lower bounds on min-entropy gap from  mentioned in Section 2 apply to random functions as well.