# Motivation for randomness extractors

I'm a maths masters student exploring how results in the geometry of finite fields, such as the finite field Kakeya conjecture, applies to randomness extractors. I'm not a computer scientist, and must admit I am getting somewhat out of my depth.

From what I have read, a randomness extractor is a function:

$E:\{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$

such that for every distribution $X$ on $\{0,1\}^n$ with minimum entropy $k$ and $Y$ (a "truly random seed") uniformly distributed on $\{0,1\}^d$, we have $E(X,Y)$ is $\epsilon$-close to a uniform distribution on $\{0,1\}^m$.

I understand the motivation to produce truly random bits, but do not understand how the concept of an extractor is useful if it already requires a truly random seed. Surely if we can already produce a truly random seed we have already solved the problem of producing truly random bits?

Also, are there any examples of an explicit use of extractors in areas such as cryptography or coding theory?

• You may want to read the first couple sections of the corresponding chapter of Salil Vadhan's Pseudorandomness monograph. – Clement C. Apr 11 '18 at 19:53
• May be it is more expensive to generate pure random bits than running the extractor function – user43170 Apr 16 '18 at 19:10

Here we have $d \ll m$, i.e., we start with a little bit of good randomness, and we end up with a lot. That's why it's called a "seed": you need something small to get you started, but you end up with a giant beautiful oak tree of randomness.
The other thing to know is that uniformly distributed bits are high-quality randomness, whereas bits with min-entropy $k$ are low-quality randomness. So an extractor says: if you start with a little bit of high-quality stuff, and a lot of low-quality stuff, you can generate a lot of high-quality stuff. That sounds potentially useful, at least in theory.