<p>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.</p>

<p>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.</p>

<p>Do cryptographers use them in practice?  Well, they could, but honestly, practitioners usually don't.  Instead, they often use hash functions (and implicitly apply some kind of random oracle assumption).  That's not as principled -- using an extractor would lead to stronger, provable guarantees -- but it's somehow similar.  You could view extractors as providing solid theoretical foundations for this sort of thing.  They also have important implications for a variety of complexity-theoretic results, which I won't try to summarize here, so extractors are certainly interesting to study.</p>

CC BY-SA 3.0
2018-04-12T09:43:30.240Z
Parenthetical question: is it known whether  randomness extractors can be built from cryptographic hash functions, at least under the simplifying assumptions  of theoretical cryptography?
Martin Berger
CC BY-SA 3.0
2018-04-12T15:13:13.390Z
@MartinBerger, in the random oracle model, it is trivial to build a randomness extractor: the random oracle (i.e., the "hash function") is itself an extractor.  In the real world, there's no proof that cryptographic hash functions behave like a good extractor, not even under any reasonable assumptions (though probably every practitioner would assume that they do, since probably every practitioner would implicitly assume something akin to the random oracle model is basically a good model of crypto hash functions).
D.W.
CC BY-SA 3.0
2018-04-12T15:39:13.643Z
Why is it difficult to show that  cryptographic hash functions behave like an extractor?
Martin Berger
CC BY-SA 3.0
2018-04-12T17:17:15.283Z
@MartinBerger, I'm not sure how to answer that question right now. In any case, I guess the comment thread is not the best place for this.  Rather than asking questions in the comment thread here, I suggest posting it as a separate question.  If you do that, perhaps it would also help if you elaborated (in that question) why you would expect it should be easy to show that, or why it would surprise you that it's not easy.
D.W.
CC BY-SA 3.0
2018-04-14T11:49:04.950Z
Thanks very much for your answer. You've certainly given me a lot more to research. However, I still don't fully understand why if we had a process to create a truly random seed, we wouldn't be able to repeat that process iteratively to create more true randomness. Maybe my issue is around how one obtains this truly random seed.
sam10269
CC BY-SA 3.0
2018-04-14T17:14:21.943Z
@sam10269, Sure, that makes sense.  Whether you can repeat that process is not really a question of theoretical computer science; it's a question of economics or physics or something.  Of course, if you can repeat it at no cost then you probably don't need an extractor.  You could think of a motivation for the theory of extractors as: in some cases it might be that you can't repeat the process, or that it would be too slow or too expensive to do so; if that happens, what can be done, at least in principle?
D.W.
CC BY-SA 3.0
2018-04-14T17:14:52.613Z
Remember that this site is for theoretical computer science, so we're especially interested in the foundations of computing, what is possible in principle, and what we can learn about the fundamentals of computation.  Engineering issues are a separate matter.  And, how to obtain a seed is a matter of engineering.  So, if that's what you're interested in, I suggest doing some research on Security.SE; you won't find answers to that here.
D.W.
CC BY-SA 3.0
2018-04-11T17:47:05.880Z
2018-04-11T17:47:05.880Z
D.W.
<p>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.</p>

<p>From what I have read, a randomness extractor is a function:</p>

<p>$E:\{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$</p>

<p>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$.</p>

<p>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?</p>

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

CC BY-SA 3.0
2018-04-11T19:53:28.433Z
You may want to read the first couple sections of the [corresponding chapter](https://people.seas.harvard.edu/~salil/pseudorandomness/extractors.pdf) of Salil Vadhan's *Pseudorandomness* [monograph](https://people.seas.harvard.edu/~salil/pseudorandomness/).
Clement C.
CC BY-SA 3.0
2018-04-16T19:10:07.217Z
May be it is more expensive to generate pure random bits than running the extractor function
user43170
<randomness><extractors>
Motivation for randomness extractors
sam10269
# Motivation for randomness extractors

(Asked by: username_0 on 2018-04-11)

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?

**Tags:** randomness, extractors
> **Comments:**
> **username_1**: You may want to read the first couple sections of the [corresponding chapter](https://people.seas.harvard.edu/~salil/pseudorandomness/extractors.pdf) of Salil Vadhan's *Pseudorandomness* [monograph](https://people.seas.harvard.edu/~salil/pseudorandomness/).  
> **username_2**: May be it is more expensive to generate pure random bits than running the extractor function  

---

## 1 answers

### Answer by username_3 on 2018-04-11. Score: 4 | Accepted answer

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.

Do cryptographers use them in practice? Well, they could, but honestly, practitioners usually don't. Instead, they often use hash functions (and implicitly apply some kind of random oracle assumption). That's not as principled -- using an extractor would lead to stronger, provable guarantees -- but it's somehow similar. You could view extractors as providing solid theoretical foundations for this sort of thing. They also have important implications for a variety of complexity-theoretic results, which I won't try to summarize here, so extractors are certainly interesting to study.

> **Comments:**
> **username_4**: Parenthetical question: is it known whether  randomness extractors can be built from cryptographic hash functions, at least under the simplifying assumptions  of theoretical cryptography?  
> **username_3**: @MartinBerger, in the random oracle model, it is trivial to build a randomness extractor: the random oracle (i.e., the "hash function") is itself an extractor.  In the real world, there's no proof that cryptographic hash functions behave like a good extractor, not even under any reasonable assumptions (though probably every practitioner would assume that they do, since probably every practitioner would implicitly assume something akin to the random oracle model is basically a good model of crypto hash functions).  
> **username_4**: Why is it difficult to show that  cryptographic hash functions behave like an extractor?  
> **username_3**: @MartinBerger, I'm not sure how to answer that question right now. In any case, I guess the comment thread is not the best place for this.  Rather than asking questions in the comment thread here, I suggest posting it as a separate question.  If you do that, perhaps it would also help if you elaborated (in that question) why you would expect it should be easy to show that, or why it would surprise you that it's not easy.  
> **username_0**: Thanks very much for your answer. You've certainly given me a lot more to research. However, I still don't fully understand why if we had a process to create a truly random seed, we wouldn't be able to repeat that process iteratively to create more true randomness. Maybe my issue is around how one obtains this truly random seed.  
> **username_3**: @sam10269, Sure, that makes sense.  Whether you can repeat that process is not really a question of theoretical computer science; it's a question of economics or physics or something.  Of course, if you can repeat it at no cost then you probably don't need an extractor.  You could think of a motivation for the theory of extractors as: in some cases it might be that you can't repeat the process, or that it would be too slow or too expensive to do so; if that happens, what can be done, at least in principle?  
> **username_3**: Remember that this site is for theoretical computer science, so we're especially interested in the foundations of computing, what is possible in principle, and what we can learn about the fundamentals of computation.  Engineering issues are a separate matter.  And, how to obtain a seed is a matter of engineering.  So, if that's what you're interested in, I suggest doing some research on Security.SE; you won't find answers to that here.  

---

