<p>First of all, see the <a href="http://en.wikipedia.org/wiki/Randomness_extractor">relevant topic</a> on Wikipedia. Secondly, you may take a look at the following paper:</p>

<p><a href="http://www.cs.haifa.ac.il/~ronen/online_papers/survey.ps">Recent developments in explicit constructions of extractors</a> by Ronen Shaltiel.</p>

<p>The paper is written in the form of a survey, and can help you find the "recent developments."</p>

<p>Finally, if all you want is a sequence of bits which "looks" random (but is not necessarily cryptographically secure), you can apply a hash function (such as MD5 or SHA-1) to your high-entropy source, and get an excellent result (for physical experiments) in almost no time.</p>

CC BY-SA 2.5
2010-12-13T12:53:33.010Z
Thanks for the hashing suggestion & links. In the links I didn't see any mention of people attempting to implement extractors. I'm very curious as to whether this is being attempted. Most extractor papers I've read mention the practical applications of extractors, yet make no reference to any attempted implementations. I'm told that the reason we've avoided hashing functions is that they are not provably random, which is very useful in the realm of MC simulations since pseudo-RNGs have shown, at times, to produce inaccurate results [ref: http://prl.aps.org/abstract/PRL/v69/i23/p3382_1 ]
Phillip Mates
CC BY-SA 2.5
2010-12-13T11:22:24.990Z
2010-12-13T11:22:24.990Z
Sadeq Dousti
<p>There is also a <a href="http://www.iacr.org/cryptodb/archive/2004/CRYPTO/1257/1257.pdf" rel="nofollow">nice paper</a> by Dodis, Gennaro, <em>et al.</em> that considers practical cryptographic primitives that can be used for extraction. They show that hash functions are not known to be good extractors, however a block cipher in CBC-MAC mode can be (with some fine-print). They also consider HMAC constructions. The approach is appealing for implementation since you can use standard cryptography libraries.</p>

<p>For CBC-MAC, the "fine-print" is roughly:</p>

<ul>
<li>Assumes the blockcipher is a psuedo-random permutation</li>
<li>Must be keyed with a truly random (but not necessarily secret) key that can be reused</li>
<li>If the output is m bits, the input must have at least 2m bits of min-entropy</li>
<li>Block length and key length must be the same (so if you are using AES, that means only AES-128 works)</li>
<li>Input length is bounded but the bound is high</li>
</ul>

CC BY-SA 2.5
2010-12-15T19:06:57.817Z
2010-12-15T19:21:25.557Z
2010-12-15T19:21:25.557Z
PulpSpy
<p>For the cryptographical pseudo-random generator case, you might also look in to <a href="http://webee.technion.ac.il/~hugo/kdf/" rel="nofollow">HKDF</a>. In the <a href="http://eprint.iacr.org/2010/264.pdf" rel="nofollow">paper</a> they discuss randomness extractors conceptually and practically, and give nice references.</p>

<p>As a side note for generating randomness for Monte Carlo, there's of course <a href="http://www.irisa.fr/caps/projects/hipsor/" rel="nofollow">HAVEGE</a>. If its bit-speed and "provability" are sufficient, you might avoid having to muck around with the quantum generators.</p>

CC BY-SA 2.5
2010-12-19T09:30:59.770Z
2010-12-19T09:45:26.607Z
2010-12-19T09:45:26.607Z
Nakedible
<p>Much of extractor literature is about minimizing the seed length, which is important for derandomization application. However, it may not be crucial for yours. Also, often the literature focuses on relatively large error (e.g., 1/100), which is fine for derandomization but may be problematic in other settings, that require an exponentially small error.</p>

<p>In your setting, it may be OK to generate once and for all a long random seed (say by tossing coins), and then use it to extract. In this case you could use pairwise independent hash functions that have rather efficient implementations. I wrote a <a href="http://www.cs.princeton.edu/~boaz/Papers/trng.pdf">paper with Shaltiel and Tromer</a> on this issue. You may also be able to use almost independent hash functions, that can be more efficient and have smaller seed. (Don't know offhand a good reference for their efficient implementation, though there have been several works on this.)</p>

<p>If you have multiple sources that are <i>independent</i>, then you can do better things. The classical Hadamard extractor works if the entropy rate is larger than 50% (this should be mentioned in the surveys above). If the entropy is smaller than 50% then we had one <a href="http://www.cs.princeton.edu/~boaz/Papers/msamples.pdf">simple construction with Impagliazzo and Wigderson</a> . The dependence between of number of sources and error achieved on the entropy rate is not ideal, though to really understand it you'll need to look at the exact bounds given by today's state of the art sum product theorems. (And if you're willing to assume certain number theoretic conjectures you can get even more efficient extractors.) This construction has been greatly improved in various ways, some of which could be relevant to your application. A great source for these is <a href="http://www.cs.washington.edu/homes/anuprao/pubs/thesis.pdf">Anup Rao's Thesis</a>.</p>

CC BY-SA 2.5
2010-12-14T13:12:39.767Z
Thanks for the well written response/overview. I've browsed over the TRNG paper you wrote with Shaltiel and Tromer. It looks quite promising. I was wondering if the paper's web page (and implementation code) is available anywhere since the link cited ( http://people.csail.mit.edu/tromer/trng/ ) in the paper doesn't contain any info on it.
Phillip Mates
CC BY-SA 2.5
2010-12-13T15:40:24.747Z
2010-12-13T15:40:24.747Z
Boaz Barak
<p>Has there been research into implementing randomness extractor constructions?</p>

<p>It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making programmatic implementations potentially unrealistic.</p>

<p>Some context:
I'm interested in using randomness extractors as a fast source of (provably?) random numbers for use in Monte Carlo simulations. We (an ETHZ Computational Physics group) have biased high-entropy sources from quantum random number generators that we would like to extract randomness from. A previous student attempted to implement a <a href="http://www.cs.berkeley.edu/~luca/pubs/t99stoc.ps">Trevisan construction</a> and ran into spacial complexity problems. Aside from that student, I have not found any reference to people trying to implement extractors.</p>

<p>Note:
I'm a CS undergrad who is very new to the area of Theoretical CS and Randomness Extractors.</p>

CC BY-SA 2.5
2010-12-13T11:28:30.743Z
You might also find arnab's answer to my question interesting: http://cstheory.stackexchange.com/questions/36/a-comparison-of-extractors-in-terms-of-tradeoffs-between-time-randomness-and-spa
Suresh Venkat
CC BY-SA 3.0
2011-04-13T06:56:50.803Z
Here it is a working implementation: http://www.wisdom.weizmann.ac.il/~neko/MAE-offline.html
didest
<reference-request><cr.crypto-security><randomness><implementation><application-of-theory>
Is there current research into the implemention of Randomness Extractors?
Phillip Mates
# Is there current research into the implemention of Randomness Extractors?

(Asked by: username_0 on 2010-12-13)

Has there been research into implementing randomness extractor constructions?

It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making programmatic implementations potentially unrealistic.

Some context:
I'm interested in using randomness extractors as a fast source of (provably?) random numbers for use in Monte Carlo simulations. We (an ETHZ Computational Physics group) have biased high-entropy sources from quantum random number generators that we would like to extract randomness from. A previous student attempted to implement a [Trevisan construction](http://www.cs.berkeley.edu/~luca/pubs/t99stoc.ps) and ran into spacial complexity problems. Aside from that student, I have not found any reference to people trying to implement extractors.

Note:
I'm a CS undergrad who is very new to the area of Theoretical CS and Randomness Extractors.

**Tags:** reference-request, cr.crypto-security, randomness, implementation, application-of-theory
> **Comments:**
> **username_1**: You might also find arnab's answer to my question interesting: http://cstheory.stackexchange.com/questions/36/a-comparison-of-extractors-in-terms-of-tradeoffs-between-time-randomness-and-spa  
> **username_2**: Here it is a working implementation: http://www.wisdom.weizmann.ac.il/~neko/MAE-offline.html  

---

## 4 answers

### Answer by username_6 on 2010-12-13. Score: 19 | Accepted answer

Much of extractor literature is about minimizing the seed length, which is important for derandomization application. However, it may not be crucial for yours. Also, often the literature focuses on relatively large error (e.g., 1/100), which is fine for derandomization but may be problematic in other settings, that require an exponentially small error.

In your setting, it may be OK to generate once and for all a long random seed (say by tossing coins), and then use it to extract. In this case you could use pairwise independent hash functions that have rather efficient implementations. I wrote a [paper with Shaltiel and Tromer](http://www.cs.princeton.edu/~boaz/Papers/trng.pdf) on this issue. You may also be able to use almost independent hash functions, that can be more efficient and have smaller seed. (Don't know offhand a good reference for their efficient implementation, though there have been several works on this.)

If you have multiple sources that are *independent*, then you can do better things. The classical Hadamard extractor works if the entropy rate is larger than 50% (this should be mentioned in the surveys above). If the entropy is smaller than 50% then we had one [simple construction with Impagliazzo and Wigderson](http://www.cs.princeton.edu/~boaz/Papers/msamples.pdf) . The dependence between of number of sources and error achieved on the entropy rate is not ideal, though to really understand it you'll need to look at the exact bounds given by today's state of the art sum product theorems. (And if you're willing to assume certain number theoretic conjectures you can get even more efficient extractors.) This construction has been greatly improved in various ways, some of which could be relevant to your application. A great source for these is [Anup Rao's Thesis](http://www.cs.washington.edu/homes/anuprao/pubs/thesis.pdf).

> **Comments:**
> **username_0**: Thanks for the well written response/overview. I've browsed over the TRNG paper you wrote with Shaltiel and Tromer. It looks quite promising. I was wondering if the paper's web page (and implementation code) is available anywhere since the link cited ( http://people.csail.mit.edu/tromer/trng/ ) in the paper doesn't contain any info on it.  

---

### Answer by username_3 on 2010-12-13. Score: 6

First of all, see the [relevant topic](http://en.wikipedia.org/wiki/Randomness_extractor) on Wikipedia. Secondly, you may take a look at the following paper:

[Recent developments in explicit constructions of extractors](http://www.cs.haifa.ac.il/~ronen/online_papers/survey.ps) by Ronen Shaltiel.

The paper is written in the form of a survey, and can help you find the "recent developments."

Finally, if all you want is a sequence of bits which "looks" random (but is not necessarily cryptographically secure), you can apply a hash function (such as MD5 or SHA-1) to your high-entropy source, and get an excellent result (for physical experiments) in almost no time.

> **Comments:**
> **username_0**: Thanks for the hashing suggestion & links. In the links I didn't see any mention of people attempting to implement extractors. I'm very curious as to whether this is being attempted. Most extractor papers I've read mention the practical applications of extractors, yet make no reference to any attempted implementations. I'm told that the reason we've avoided hashing functions is that they are not provably random, which is very useful in the realm of MC simulations since pseudo-RNGs have shown, at times, to produce inaccurate results [ref: http://prl.aps.org/abstract/PRL/v69/i23/p3382_1 ]  

---

### Answer by username_4 on 2010-12-15. Score: 4

There is also a [nice paper](http://www.iacr.org/cryptodb/archive/2004/CRYPTO/1257/1257.pdf) by Dodis, Gennaro, *et al.* that considers practical cryptographic primitives that can be used for extraction. They show that hash functions are not known to be good extractors, however a block cipher in CBC-MAC mode can be (with some fine-print). They also consider HMAC constructions. The approach is appealing for implementation since you can use standard cryptography libraries.

For CBC-MAC, the "fine-print" is roughly:

* Assumes the blockcipher is a psuedo-random permutation
* Must be keyed with a truly random (but not necessarily secret) key that can be reused
* If the output is m bits, the input must have at least 2m bits of min-entropy
* Block length and key length must be the same (so if you are using AES, that means only AES-128 works)
* Input length is bounded but the bound is high


---

### Answer by username_5 on 2010-12-19. Score: 3

For the cryptographical pseudo-random generator case, you might also look in to [HKDF](http://webee.technion.ac.il/~hugo/kdf/). In the [paper](http://eprint.iacr.org/2010/264.pdf) they discuss randomness extractors conceptually and practically, and give nice references.

As a side note for generating randomness for Monte Carlo, there's of course [HAVEGE](http://www.irisa.fr/caps/projects/hipsor/). If its bit-speed and "provability" are sufficient, you might avoid having to muck around with the quantum generators.


---

