Is there current research into the implemention of Randomness Extractors?

Question

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

Answer 1

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

Answer 2

First of all, see the relevant topic on Wikipedia. Secondly, you may take a look at the following paper:

Recent developments in explicit constructions of extractors 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.

Answer 3

There is also a nice paper 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 4

For the cryptographical pseudo-random generator case, you might also look in to HKDF. In the paper 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. If its bit-speed and "provability" are sufficient, you might avoid having to muck around with the quantum generators.