2
$\begingroup$

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?

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

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Parenthetical question: is it known whether randomness extractors can be built from cryptographic hash functions, at least under the simplifying assumptions of theoretical cryptography? $\endgroup$ – Martin Berger Apr 12 '18 at 9:43
  • 1
    $\begingroup$ @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). $\endgroup$ – D.W. Apr 12 '18 at 15:13
  • $\begingroup$ Why is it difficult to show that cryptographic hash functions behave like an extractor? $\endgroup$ – Martin Berger Apr 12 '18 at 15:39
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W. Apr 12 '18 at 17:17
  • 1
    $\begingroup$ @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? $\endgroup$ – D.W. Apr 14 '18 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.